本文内容参考《算法导论》，OI Wiki。（数学好难，暂时搁置）
快速幂
例题
整数
时间复杂度：\(O(\log{n})\)。
1 | private static final long MOD = 1_000_000_007; |
矩阵
时间复杂度：\(O(\log{n})\)。
1 | private static final int MOD = 1_000_000_007; |
数论
例题
判断质数
时间复杂度 \(O(n\sqrt{n})\)。
1 | private static boolean isPrime(int x) { |
质数筛法
埃氏筛
时间复杂度 \(O(n\log{\log{n}})\)，筛掉质数的倍数，每个合数都会被筛它的质因数的个数次。
1 | private static boolean[] sieveOfEratosthenes(int n) { |
欧拉筛
时间复杂度 \(O(n)\)，每个合数都只被它的最小质因数筛掉。
1 | private static boolean[] sieveOfEuler(int n) { |
分解质因数
时间复杂度 \(O(\sqrt{n})\)。
1 | private static Map<Integer, Integer> primeFactors(int x) { |
欧拉函数
欧拉函数 \(\phi(n)\)，表示 \([1,n]\) 范围内和 \(n\) 互质的数的个数，有如下性质：
- 若 \(\gcd(a,b)=1\)，则 \(\phi(a\times b)=\phi(a)\times \phi(b)\)。
- 若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，其中 \(p_{i}\) 为质数，则 \(\phi(n)=n\times\prod_{i=1}^{k}(1-\frac{1}{p_{i}})\)。
我们可以使用分解质因数求解某个数的欧拉函数，时间复杂度为 \(O(\sqrt{n})\)；也可以使用欧拉筛来求解 \([1,n]\) 范围内所有数的欧拉函数，时间复杂度为 \(O(n)\)。在欧拉筛中，每个合数都是被它的最小质因子筛掉，设 \(p\) 是 \(n\) 的最小质因子，则 \(n=n^{\prime}\times p\)，分类讨论：
- 如果 \(n^{\prime}\bmod p\neq 0\)，因为 \(p\) 是质数，所以 \(\gcd(n^{\prime},p)=1\)，则 \(\phi(n)=\phi(n^{\prime})\times \phi(p)=\phi(n^{\prime})\times (p-1)\)。
- 如果 \(n^{\prime}\bmod p=0\)，则 \(\phi(n)=p\times n^{\prime}\times\prod_{i=1}^{k}(1-\frac{1}{p_{i}})=p\times \phi(n^{\prime})\)。
1 | private static int[] sieveOfEuler(int n) { |
最大公约数
欧几里得算法
时间复杂度 \(O(\log{\max(a,b)})\)。求得最大公约数之后，使用 \(\gcd(a,b)\times\operatorname{lcm}(a,b)=a\times b\) 公式可以得到最小公倍数。
1 | private static int gcd(int a, int b) { |
扩展欧几里得算法
常用于求解 \(ax+by=\gcd(a,b)\) 的一组解。
1 | private static int x, y; |
其他知识
约数个数
若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，则 \(d_{n}=\prod_{i=1}^{k}(c_{i}+1)\)。
约数之和
若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，则 \(s_{n}=\prod_{i=1}^{k}\sum_{j=0}^{c_{i}}{p_{i}^{j}}\)。
裴蜀定理
若 \(a,b\) 是整数，则对于任意的整数 \(x,y\)，\(ax+by\) 总是 \(\gcd(a,b)\) 的倍数，并且存在整数 \(x,y\)，使得 \(ax+by=\gcd(a,b)\)。特别的，若存在整数 \(x,y\) 使得 \(ax+by=1\)，则 \(\gcd(a,b)=1\)，即 \(a,b\) 互质。
费马小定理
若 \(p\) 是质数，\(\gcd(a,p)=1\)，则 \(a^{p-1}\equiv 1\pmod{p}\)。
欧拉定理
若 \(\gcd(a,n)=1\)，则 \(a^{\phi(n)}\equiv 1\pmod{n}\)。
模乘法逆元
若 \(p\) 是质数，根据费马小定理，有 \(a\times a^{-1}\equiv 1\equiv a^{p-1}\pmod{p}\)，得到 \(a^{-1}\equiv a^{p-2}\pmod{p}\)。
若 \(b\) 是任意整数，求 \(a\) 的逆元，等价于求 \(ax\equiv 1\pmod{b}\) 的解，等价于求 \(ax+by=1\) 的解。如果 \(\gcd(a,b)=1\)，则可以使用扩展欧几里得算法求解该方程。如果 \(\gcd(a,b)\neq 1\)，根据裴蜀定理可知方程无解（或者可以将方程变换为 \(\frac{a}{g}x+\frac{b}{g}y=\frac{1}{g}\)，等式左边是整数，右边不是整数，方程无解），即逆元不存在。
线性同余方程
求 \(ax\equiv c\pmod{b}\) 的解，等价于求 \(ax+by=c\) 的解，同样的，当 \(\gcd(a,b)\mid c\) 时方程有解。使用扩展欧几里得算法可以求出 \(ax+by=\gcd(a,b)\) 的解，然后将方程变换为 \(a\frac{c}{\gcd(a,b)}x_{0}+b\frac{c}{\gcd(a,b)}y_{0}=c\)，可以得到方程的解。