数论

说明比较草率，主要说关键步骤，不太严谨。

基础数论

Miller-Rabin

概率性判断正整数 $n$ 是否为素数。

前置：

费马小定理：$a^{p-1}\equiv 1\pmod{p}$。
二次探测定理：若 $p$ 为奇素数，$x^2\equiv1\pmod{p}$ 的解有且仅有 $\pm1$。

首先排除 $n=2k$ 或 $n<0$ 的情况。

将 $n-1$ 分解为 $u\times2^t$。

对 $n$ 进行 $k$ 轮测试，每轮过程如下：

在 $[2, n-1]$ 随机一个底数 $a$，计算出 $x=a^u \bmod n$。
1. 若 $x=1$，则必然满足 $a^{n-1}\equiv1\pmod{n}$，通过此轮测试。
2. 否则，进入第二步。
若 $n$ 为素数必然有 $a^{u\times2^t}\equiv 1\pmod{n}$，我们默认 $a^{n-1}\equiv1\pmod{n}$。
可以至多循环 $t$ 轮，每轮如下：
1. 设当前为第 $k$ 轮，则 $x=u\times2^{k-1}$。
  检测 $x$ 是否等于 $n-1$。若等于，则符合 $a^{n-1}\equiv1\pmod{n}$。跳出循环，通过测试。
2. $x\gets x\times x\bmod n$。
若循环了 $t$ 次，都没有出现 $x=n-1$ 的情况，说明我们从 $a^{u}\not=1$ 不断平方，不经过 $-1$ 却得到了 $a^{n-1}\equiv1\pmod{n}$，说明存在某个 $x$，使得 $x^2=1$，且 $x\not=\pm1$，这与二次探测定理不符，说明 $n$ 不为奇素数。不通过测试。

上述过程时间复杂度 $O(k\log^3n)$。

必读：论 Miller-Rabin 算法的确定性化，Miller-Rabin 素性测试上限（OEIS）

选前 $12$ 个质数可以保证在 long long 范围内判断不出错。

提供一个自认为清晰的写法：

inline bool millerRabin(LL x) {
	if(x < 2 || !(x&1)) return x==2;
	LL d = x-1; int t = 0;
	while(!(d&1)) d>>=1, ++t;
	for(int i=1, j;i<=12;++i) {
		if(x == primes[i]) return true;
		if(x%primes[i] == 0 || qpow(primes[i], x-1, x) != 1) return false;
		LL u = qpow(primes[i]%x, d, x);
		if(u == 1) continue;
		for(j=0;j<t;++j) {
			if(u == x-1) break;
			u = (LLL)u*u%x;
		}
		if(j >= t) return false;
	}
	return true;
}

Pollard-Rho

对 $n$ 进行质因数分解。

前置：

生日悖论：在 $[1, n]$ 中等概率随机生成 $\sqrt{n}$ 个数，有 $50\%$ 的概率出现重复。

用函数 $f(x)=x^2+c\bmod n$ 生成序列 $\{x_n\}$（$x_1$ 任取， $x_i=f(x_{i-1})$，$c$ 是随机常数），会生成长得像 $\rho$ 的序列：

图源 oi-wiki

注意到 $f(x)$ 是近乎等概率（伪）随机的，所以这个 $\rho$ 的期望长度为 $O(\sqrt{n})$。

首先考虑一般的质因数分解，是枚举到 $\sqrt{n}$，判断每个数是否能被整除。在最坏情况下是 $O(\sqrt{n})$ 的（比如 $n$ 为质数或 $n=p^2$）。

所以要先用 Miller-Rabin 排除 $n$ 为质数的情况。

记 $m$ 为 $n$ 的最小非平凡质因数，有 $m\le\sqrt{n}$。

记一个新序列 $\{y_n\}$，其中 $y_i=x_i\bmod m$，可以发现仍满足 $y_i=y_{i-1}^2+c\bmod m$。

若任取两个位置 $i,j$（$i\not=j$），若 $y_i=y_j$ （此处取到的概率为 $O(\sqrt{m})\le O(n^\frac{1}{4})$，由生日悖论可得），则 $\left|x_i-x_j\right|=km$。那么通过 $\gcd(\left|x_i-x_j\right|, n)$ 可以得到 $n$ 的一个因数 $m$。

也就是说，如果在 $\rho$ 上跑，期望在 $O(\sqrt{m})$ 次内搞出一个因数。

然后是如何在 $\rho$ 上跑的问题。

Floyd 判环

我们考虑两个人在长为 $\sqrt{n}$ 的圈上跑，从 $x_1$ 同时同向出发，一个步长为 $2$，一个步长为 $1$，可以发现在 $\sqrt{n}$ 步后两人就会相遇。同理可以在 $\rho$ 上放两个标记这样跑，最后必定会重合（重合时就退出），在路上将两个标记代表的 $x_i,x_j$ 拿出来做 $\gcd$，抓到因数就直接返回。期望是 $O(n^\frac{1}{4}\log n)$ 的。

倍增优化

要理解这个东西的话，更推荐看代码。

另一种想法是，指定一个人待在起点，另一个绕圈跑。将每次得到的 $\left|x_i-x_0\right|$ 乘起来取模，有个神奇的性质是这样取模并不会改变 $\gcd$。所以隔多次后再取 $\gcd$。然后将 $x_0$ 改变为当前的 $x_t$。常数会小点。

inline LL f(LL x, LL c, LL mod) { return ((LLL)x*x+c)%mod; }
mt19937_64 rrand(114514);
inline LL pollardRho(LL x) {
	LL s = 0, t = 0, val, c = rrand()%(x-1)+1;
	for(int goal = 1; ; goal <<= 1, s = t) {
		val = 1;
		for(int step = 1; step <= goal; ++step) {
			t = f(t, c, x);
			val = (LLL)val * abs(t-s) % x;
			if(!(step%127)) {
				LL d = gcd(val, x);
				if(d > 1) return d;
			}
		}
		LL d = gcd(val, x); // 当 val == 0 时，返回 x，表示分解失败，应重新随机一个 c 进行分解
		if(d > 1) return d;
	}
}

裴蜀定理 & exGCD

定理内容：$a,b$ 是不全为 $0$ 的整数，存在整数 $x,y$ 使得 $ax+by=\gcd(a,b)$。

拓展欧几里得：我们考虑找出这样一组解 $(x,y)$。

考虑两个方程

\[\left\{\begin{matrix} ax_1+by_1&=&\gcd(a,b)\\ bx_2+(a\bmod b)y_2&=&\gcd(b,a\bmod b) \end{matrix}\right. \]

显然右边一样，我们把它化为一个整式：

\[ax_1+by_1=bx_2+(a-\lfloor\frac{a}{b}\rfloor b)y_2 \]

展开……

\[ax_1+by_1=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2) \]

于是我们大胆地让 $y_2=x_1$，$y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2$，当知道 $x_2,y_2$ 时，一组可行解就诞生了。~~似乎还是最小整数解？（存疑~~

显然最后会出现 $a=0,b=d$ 地情况，此时的解是 $(0,1)$，递归上去就好了。

自认为清晰的写法（建议背诵）：

void exgcd(int a, int b, int& x, int& y) {
    if(!b) return x = 1, y = 0, void();
    exgcd(b, a%b, y, x); y -= a/b*x;
}

最后的 y -= a/b*x 建议熟练背诵。我经常把 y 和 x 写反。

记住这里 y 和 x 的顺序与递归下去的 exgcd(b, a%b, y, x) 的顺序相同。

(ex)CRT

能干啥：给定 $k$ 组 $(a_i, n_i)$，求解下列线性同余方程：

\[\begin{cases} x&\equiv &a_1\pmod{n_1}\\ x&\equiv &a_2\pmod{n_2}\\ &\vdots&\\ x&\equiv &a_k\pmod{n_k} \end{cases} \]

CRT

当 $n_i$ 互质时，流程如下：

记：$ n = \prod_{i=1}^kn_i$
对每个方程：
1. 记 $m_i=\frac{n}{n_i}$
2. 求解 $m_i$ 在 $\bmod{n_i}$ 意义下的逆元 $m_i^{-1}$
3. 记 $R_i=m_i\times m_i^{-1}$ （不对 $n_i$ 取模）
唯一解为 $x\equiv\sum_{i=1}^ka_iR_i\pmod{n}$

将 $x$ 代入每个方程就可以得到证明。$R_i$ 仅在模数是 $n_i$ 时为 $1$，否则为 $0$。

exCRT

$n_i$ 不互质。

必读：rxz

出现了非常愚蠢的错误导致心态崩了：

\[\begin{cases} a_1 + k_1n_1 = x\\ a_2 + k_2n_2 = x \end{cases} \]

设 $d = \gcd(n_1,n_2)$，$r_1=\frac{n_1}{d},r_2=\frac{n_2}{d}$：

\[k_1r_1 - k_2r_2 = \frac{a_2-a_1}{d} \]

然后左边可以用 exGCD 求解。愚蠢的错误是指右边的 $a_2-a_1$ 我取了绝对值。

提供一个比较清晰的实现想法，用 $u$ 和 $M$ 记录下合并前 $i$ 同余方程为 $x \equiv u \pmod{M}$，然后再和下个方程合并，初始化一下即可。

这个东西不管我怎么写都感觉不太清晰，就不放代码了。

待填坑：「如何清晰明了地理解为什么最后要取 $\operatorname{lcm}$，以及对于这整个算法我的思路流程」

逆 CRT

考虑现在有 $n$ 个线性同余方程形如 $x \equiv a_i \pmod{m_i}$，其中 $a_i<m_i, m_i\le 10^6$，判断是否有正整数解。即这 $n$ 个线性同余方程是否冲突。

显然有一个 $\mathcal O(n^2)$ 的做法，两两判断 $\gcd(m_i, m_j)\mid a_i-a_j$，显然爆炸。

考虑逆 CRT，对于模数 $m$，唯一分解成如下：

\[m=\prod_{i=1}^k p_i^{\alpha_i} \]

然后方程可以拆分为：

\[\left\{\begin{matrix} x \equiv a \pmod{p_1^{\alpha_1}}\\ x \equiv a \pmod{p_2^{\alpha_2}}\\ \vdots\\ x \equiv a \pmod{p_k^{\alpha_k}} \end{matrix}\right. \]

显然，这 $k$ 组同余方程经过 CRT 合并后就会得到 $x \equiv a\pmod{m}$。这两个是一一对应或者说充要的。

这时候，任意两个同余方程之间模数互质，一定可以合并，问题在于拆了若干个 $m$ 后，同一个素数幂模数可能会有不同的 $a$，此时显然同余方程无解。

还有另一种可能：对于同一个素数，不同幂次也可能有相互排斥的 $a$。比如 $x\equiv 1\pmod{2}$ 且 $x\equiv 2\pmod{4}$。

考虑拆解同余方程的时候，不止拆成 $k$ 个，而是对于每个素数的每个幂都拆一个，即拆 $\sum_{i=1}^k \alpha_i$ 个。

$m$ 拆分出来的同余方程个数显然等于可重的质因数数量，$\mathcal O(\log W)$ 级别的。

总同余方程数 $\mathcal O(n\log n)$，上界很松，常数很小，一般多加一个 map 的 $\log$ 也没啥问题。

其他

因为 CRT 可以合并同余方程的性质，它还可以用在其它地方，如三模数 NTT，ex-Lucas 等，建议感性理解这种套路。

(ex)BSGS

求解方程：

\[a^x\equiv b\pmod{m} \]

普通 BSGS（$a\bot m$）：

将可行解 $x$ 拆分为 $pS-q(0\le q<S)$，方程变为：

\[a^{pS}\equiv a^qb\pmod{m} \]

用哈希表记录下同余式右边的 $S$ 种取值，然后在同余式左边从 $a^S$ 开始不断乘上 $a^S$，看一下左右是否能相等。左边需要乘 $\frac{m}{S}$ 次，右边要存 $S$ 个，显然 $S=\sqrt{m}$ 的时候会比较优，具体情况具体分析吧。

如果 $a\not\bot m$，不能用上面的做法，但可以把它弄到 $a\bot m$，具体如下：

\[a^x\equiv b\pmod{m} \]

记 $d_1=\gcd(a, m)$，在同余式上同除 $d_1$，如果 $d_1\not\mid b$，则无解，否则：

\[\frac{a}{d_1}a^{x-1}\equiv \frac{b}{d_1}\pmod{\frac{m}{d_1}} \]

如果还不互质，继续这样，记 $d_2=\gcd(a, \frac{m}{d_1})$，如果 $d_2\not\mid \frac{b}{d_1}$，则无解……

\[\frac{a^k}{d_1d_2\cdots d_k}a^{x-k}\equiv\frac{b}{d_1d_2\cdots d_k}\pmod{\frac{m}{d_1d_2\cdots d_k}} \]

显然不会除超过 $\log m$ 次，效率可以保证。

我们记除到某一次时变为：

\[Aa^{x-k}\equiv b'\pmod{m'} \]

如果出现 $A\equiv b'\pmod{m'}$，显然可以直接返回 $x=k$。

否则，一直除直到 $a$ 和 $m'$ 互质。

这时候，发现 $A$ 的分子都是 $a$，所以 $A\bot m'$，可以直接把 $A$ 乘上 $\varphi(m')-1$ 逆元过去（这里是 $\varphi(m')$，不是 $m'-2$）

然后变成：

\[a^{x-k}\equiv b''\pmod{m'} \]

这时候直接普通 BSGS 干上去，最后 $x\leftarrow x+k$ 就好了。

必刷：洛谷某题单

不贴代码。记得特判 $b=1$ 和 $m=1$。

其它

BSGS 的思想值得学习，其它的应用场景有光速幂等。

光速幂：多次询问 $a^x\bmod m(m\not\in\text{prime})$，可以把 $x$ 分成 $pS+q$ 的形式，然后处理 $a^{kS}$ 和 $a^k$，可以做到一次乘法算出答案。

然后是我的 yy 时间：BSGS 能否用在形如求 $a$ 是斐波那契数列的第几项这样的问题上呢？预处理出递推的矩阵，然后对 $a$ 求个逆看下在不在哈希表里？

ex-BSGS 的思想也值得学习，不互质就硬除，搞到互质，比如 ex-Lucas 中有所体现。

(ex)Lucas 定理

定理内容（$p\in{\text{prime}}$）：

\[\binom{n}{m}\bmod p=\binom{n\bmod p}{m\bmod p}\times\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\bmod p \]

这个证明可能也许大概可以掰扯一下，但是，是我根据自己的印象 yy 出来的，请勿被误导。

根据二项式定理，显然有 $\binom{n}{m}$ 是 $(1+x)^n$ 的 $x^m$ 项系数。类似上面刚说的 BSGS，把 $n$ 拆为 $kp+c(0\le c<p)$，$m$ 拆为 $ap+b(0\le b<p)$ 然后就变成：

\[\underbrace{(1+x)^p(1+x)^p\cdots(1+x)^p}_{\lfloor\frac{n}{p}\rfloor\text{个}}\times\underbrace{(1+x)(1+x)\cdots(1+x)}_{n\bmod p\text{个}} \]

就相当于在前面的 $k$ 个选 $a$ 个，后面的 $c$ 个选 $b$ 个吧，差不多就这么个意思。

ex 内容

若 $p\not\in\text{prime}$。

先将 $p$ 唯一分解掉，变成：

\[\prod p_i^{\alpha_i} \]

然后如果能计算出对 $p_i^{\alpha_i}$ 取模的结果，就能直接 CRT 合并辣！

将组合数写成阶乘：

\[\binom{n}{m}=\frac{n!}{m!(n-m)!}\bmod p^\alpha \]

下面的阶乘不能搞逆元。像 ex-BSGS，想办法弄到能搞逆元：

\[\frac{\frac{n!}{p^x}}{\frac{m!}{p^y}\frac{(n-m)!}{p^z}}\times p^{x-y-z}\bmod p^\alpha \]

然后变成求形如：

\[\frac{n!}{p^x}\bmod p^\alpha \]

必读：oi-wiki 中举的例子只能说是非常好了

\[\frac{n!}{p^x}\equiv \frac{\lfloor\frac{n}{p}\rfloor!}{p^{x'}}\times\left(\prod_{i\bot p}^{p^\alpha}i\right)^{\lfloor\frac{n}{p^\alpha}\rfloor}\times\left(\prod_{i\bot p}^{n\bmod p^\alpha}i\right) \]

暴力走循环节，然后递归求解。

关于这个为什么循环，这里可以给出我的一个想法：

\[1\times2\times4\times5\times7\times8\equiv(1+9)\times(2+9)\times(4+9)\times(5+9)\times(7+9)\times(8+9)\pmod{9} \]

可以发现右边如果运用乘法分配律，展开就是左边了（选了 $9$ 就会被消掉）。

~~根据上述过程，直接做，随便做。~~

给出自认为常数优秀正常的计算 $\frac{n!}{p^x}\bmod p^\alpha$ 的代码（calc）：

// p: p^\alpha
// lp: p
inline void work(int p, int lp) {
	prod[0] = 1;
	for(int i = 1; i <= p; ++i)
	if(i % lp) prod[i] = mul(i, prod[i-1]);
	else prod[i] = prod[i-1];
}
int calc(LL n, int p, int lp) {
	if(n == 0) return 1;
	int res = qpow(prod[p], n/p); 
	res = mul(res, prod[n%p]);
	res = mul(res, calc(n/lp, p, lp));
	return res;
}

其它

~~目前并没有找到 ex-Lucas 的想法有哪些地方能加以拓展应用。~~

求 $\frac{n!}{p^x}$，其中 $p \nmid \frac{n!}{p^x} $ 且 $\frac{n!}{p^x}\in\mathbb {Z}$。

阶与原根

真没啥好讲，建议出门左转 oi-wiki。

数论函数

概念。

积性函数：$\forall \gcd(x,y)=1,f(xy)=f(x)f(y)$，$f(1)=1$。
- 常见的有：$\sigma_k(n),\varphi(n),\mu(n),\epsilon(n)$
完全积性函数：$\forall x,y\in\mathbb{N^+},f(xy)=f(x)f(y)$。
- 常见的有：$id_k(n)$

埃氏筛

memset(flg, 0, sizeof(flg));
flg[1] = 1;
for(int i = 2; i <= n; ++i)
    if(!flg[i])
        for(int j = i*i; j <= n; j += i)
            flg[j] = 1;

原理：对于质数 $i$，筛掉其所有倍数。

时间复杂度 $\mathcal O(n\log\log n)$，不会证。可以感性理解，一个数显然会被筛多次，如 $60$ 会被 $2,3,5$ 筛，显然大于 $\mathcal O(n)$，但也只有质数才会被拿去筛倍数，显然小于 $\mathcal O(n\ln n)$。

其它

忘了。

欧拉筛

memset(flg, 0, sizeof(flg));
flg[1] = 1;
for(int i = 2; i <= n; ++i) {
    if(!flg[i]) pr[++tot] = i;
    for(int j = 1; j <= tot && i * pr[j] <= j; ++j) {
        flg[i*pr[j]] = 1;
        if(i%pr[j] == 0) break;
    }
}

原理：对于任意数 $n$，数 $n$ 只会被自己的最小质因数 $pr[j]$ 和 $i=n/pr[j]$ 的时候筛掉。

一个数只会被筛一次，时间复杂度 $\mathcal O(n)$。

亚线性筛法

指在低于 $\mathcal O(n)$ 的时间复杂度内求出一些积性函数的前缀和。

$\mathcal O(1)$ 瞪眼法

求积性函数 $id(n)$ 的前缀和。

$S_0(n)=\sum_{i=1}^n1=n$；

$S_1(n)=\sum_{i=1}^ni=\frac{n(n+1)}{2}$；

$S_2(n)=\sum_{i=1}^ni^2=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}$；

$S_3(n)=\sum_{i=1}^ni^3=S_1^2(n)$；

$\sum_{i=1}^n\epsilon(i)=[n\ge 1]$。

2022/3/5：本质上是总结自己学习过程中参考的学习资料和目前见到的套路。

2022/5/5：补充 ex-Lucas 其它用法，求解类似阶乘除掉某个素数。补充（逆）CRT。添加数论函数块。

number-theory

数论