复习一下数论中的知识点。
欧拉函数
定义：\(\leq n\) 且与 \(n\) 互质的数的个数
性质：
- 是积性函数：\(\forall gcd(a, b) = 1\)，有 \(\phi(ab) = \phi(a)\phi(b)\)
- 欧拉定理：\(gcd(a, p)=1\) 时，\(a^{\phi(p)} \equiv 1\space (mod \space p)\)
求解：\(\phi(n) = n * \prod_{i=1}^{s} \frac{p_{i}-1}{p_{i}}\)，\(p_{i}\) 是 \(n\) 的质因子
同余相关
线性同余方程
形式：\(ax \equiv b\space(mod \space n)\)
更形象些的理解：
- \(ax \% n = bx\%n\)
- \(ax+ny=b\)
- 二者相差值是 \(n\) 的倍数
假设上式中 \(a,b,n\) 均已知，求 \(x\) 的通解：
-
无解情况：\(d=gcd(a,n) \nmid b\)
证明：\(ax\) 一定是 \(d\) 的倍数，而 \(b\) 不是 \(d\) 的倍数，因此二者的差一定不是 \(d\) 的倍数。而 \(n\) 是 \(d\) 的倍数，同余式要求二者的差一定是 \(n\) 的倍数，故也必须是 \(d\) 的倍数，矛盾。
-
有解：
- \(gcd(a, n) = 1\) 时，由于 \(a\) 一定存在逆元，因此两边同乘 \(a^{-1}\)，即可得到：\(x = ba^{-1} \% \space n\)。
- \(gcd(a, n) > 1\) 时，可以将 \(a,b,n\) 同除以 \(d\)，得到新的同余式，仍与原式等价；此时 \(gcd(a',n')=1\)，再用方法 \(1\) 求解 \(x\) 即可：\(x = b' (a')^{-1} \% \space n'\)。
通过上述方法可以得到原同余式的一个特解 \(x_{0}\)，观察两种有解的情况，求得特解的模数均为 \(\frac{n}{d}\)，其中 \(d = gcd(a, n)\)，因此同余式 \(ax \equiv b\space(mod \space n)\) 的通解为：
求最小非负整数解：将任意特解 \(x_{0}\) 对 \(\frac{n}{d}\) 做“模加模”即可。
以上利用了逆元来求解，还有一种不定方程的解法，见 oi-wiki
逆元
定义：
\(ax \equiv 1\space(mod \space n)\)，使得该式成立的正整数 \(x\)。
存在性：当且仅当 \(gcd(a,n)=1\)，即 \(a,n\) 互质时，\(a\) 模 \(n\) 意义下的逆元存在。
求解逆元：
-
快速幂（仅适用于模数是质数）
复杂度：\(O(\log M)\)
-
扩欧（任何情况下均适用）
复杂度：\(O(\log(min\{a,M\}))\)
费马小定理
定义：对于 \(\forall\) 质数 \(p\)，若 \(p \nmid a\)（等价于 \(a,p\) 互质，因为 \(p\) 一定是质数），则：
欧拉定理
定义：对于 \(\forall\) p, 若 \(a, p\) 互质，则：
不难看出，费马小定理就是欧拉定理的一个特例，因为对于质数 \(p\), \(\phi(p) = p - 1\)。
扩展欧拉定理
适用于任何情况，即使 \(a,p\) 不互质。
oi-wiki
阶，原根
类欧几里得算法
看这个博客就行：blog