目录
数论
整除
如果 $k_{1},k_{2}$ 互质，则 $k_{1}+k_{2}$ 与 $k_{1}×k_{2}$ 互质。
在自然数集中，小于 $n$ 的质数约有 ${\frac {n} {ln(n)}}$ 个。
切比雪夫定理
$1.$ 对整数 $n＞3$ ，则至少存在一个质数 $p$ ，符合 $n＜p＜2n-2$ 。
$2.$ 对任意自然数 $n > 6$ ， 至少存在一个 $4k + 1$ 型和一个 $4k + 3$ 型素数 $p$ 使得 $n < p < 2n$ 。
$3.$ 对任意自然数 $k$ ， 存在自然数 $N$ ， 对任意自然数 $n > N$ 至少存在 $k$ 个素数 $p$ 使得 $n < p < 2n$ 。
$Miller-Rabin$
$Miller-Rabin$ 的复杂度是 $O(klogn)$ ，其中 $k$ 是测试次数。
质数筛法
埃氏筛
思想： 从小到大枚举分析每一个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。
int v[N]; void primes(int n) { memset(v, 0, sizeof v); for(int i = 2;i <= n; ++ i){ if(v[i])continue; for(int j = i;j <= n / i; ++ j) v[i * j] = 1; } }
时间复杂度： $O(nlog_{10}log_{10}n)≈O(n)$ ，所以它的时间复杂度其实是劣于线性筛的。这里补充自然数以及合数的和都是 $O(log_{10}n)$ ，质数为 $O(log_{10}log_{10}n)$ 。
虽然其时间复杂度比较劣，但这种思想是很值得学习的。如果需要筛一个 $[L,R]$ 的区间内的素数，我们需要先看 $sqrt(R)$ 的范围，然后预处理出这个范围内的素数。然后从小到大枚举素数，找到不小于 $L$ 的最小 $p$ 的倍数，且不能是 $p$ 本身，然后按照这个筛法打标记，复杂度是 $O(R-L+{\sqrt {R}})$ 。代码如下：
memset(st, 0, sizeof st); for (int i = 0; i < cnt; i ++ ) { LL p = primes[i];// 先筛一遍 for (LL j = max(p * 2, (l + p - 1) / p * p); j <= r; j += p) st[j - l] = true; }
线性筛（欧拉筛）
扫到一个数字 $i$ 时，如果没有标记过，则为质数。
不然 $i$ 为合数，考虑将质数数组中从小到大开始给 $i×prime[j]$ 打标记，直到 $i%prime[j]==0$ ，这时我们找到了 $i$ 的最小质因子 $prime[j]$ ，在此之前的质因子全都比 $i$ 的最小质因子要小，所以打标记的数字，都是因为枚举到了这个数字的最小质因子才打的，之后的数字，因为都比最小质因子要大，所以不打标记，直接 $break$ 。所以每个数字因为只有一个最小质因子，所以只枚举了一次，复杂度为 $O(n)$ 。并且我们在筛的同时，也拿到了 $1~n$ 每个数字的最小质因子。
const int N = 10005; int n, primes[N], cnt,min_prime[N]; bool vis[N]; inline void get_prime() { for(register int i = 2; i <= n; i ++) { if(!vis[i]) primes[ ++ cnt] = i; for(register int j = 1; j <= cnt && i * primes[j] <= n; ++ j) { vis[i * primes[j]] = 1; if(i % primes[j] == 0) { min_prime[i]=prime[j];// 最小质因子 break; } } } }
反素数
如果 $n$ 是 $1…n$ 中正约数个数最多的数，且唯一，也就是约数最多且最小，那么 $n$ 就是反素数。
若 $N≤2^{31}$ ， $1…N$ 中任何数的不同质因子都不会超过 $10$ 个且所有质因子的质数都不会超过 $30$ 。因为光 $2$ 乘到 $31$ 这个数都比 $N$ 大。所以反素数都可以表示为 $2^{c_{1}}×3^{c_{2}}×5^{c_{3}}×7^{c_{4}}×11^{c_{5}}×13^{c_{6}}×17^{c_{7}}×19^{c_{8}}×23^{c_{9}}×29^{c_{10}}$ ，其中 $c$ 数组递减。
所以我们可以直接 $dfs$ 找到前十个质数
例 $1$
题目
给定一个正整数 $n$ ，输出最小的整数，满足这个整数有 $n$ 个因子，即求因子数一定的最小反素数。
题解
按上面的剪剪枝，乱写就行了。
$Pollard Rho$
时间复杂度 $O(n^{\frac {1} {4}})$ ，用来找到 $n$ 的一个素因子 $p$ ，每次找到就一直除它，最不利的情况是每个素因子都是一次幂，所以全部分解的复杂度正常是 $O(n^{\frac {1} {4}}logn)$ 的，但因为质因数越多的时候大小都不一样，正常的对数级别的最后实际上也就是常数级别的影响，所以完全分解也可以看作是 $O(n^{\frac {1} {4}})$ 的。
例 $2$
题目
https://nanti.jisuanke.com/t/42544
给 $t$ 组数据 $(t≤8)$ ，每组数据给一个 $n,x,y,n≤10^{5},2≤x,y≤10^{18}$ ，代表一个长度为 $n$ 的数组 $a_{i},a_{i}≤10^{18}$ ，且保证 $a_{i}$ 之和小于 $y$ 。现在定义 $Z={\prod_{i=1}^{n}}a_{i}!$ 。求最大的 $i$ ，使得 $(Z×X^{i})|Y!$ 。
题解
显然对着一堆阶乘使劲是不可以的，显然 $Y!$ 可以约掉 $Z$ 所有的因子。剩下看 $X$ 都有什么因子，然后提前处理出 $Y!$ 和 $Z$ 中这些因子的幂次，做一个差，然后取所有剩余幂次/一个 $X$ 中有多少个幂次，就是能取多少个 $X$ ，然后取最小值就是答案。而 $X$ 的质因数分解，显然需要 $pollard_rho$ 。
竟然一遍过了 $×$ 。
威尔逊定理
若 $p$ 为素数，则 $(p-1)!+1 ≡ p(mod p)$ 。
原根
如果 $a$ 模 $m$ 的阶等于 $\phi(m)$ ，则称 $a$ 为模 $m$ 的一个原根。素数一定有原根，原根不唯一，部分合数也有原根。
$1000000007$ 的原根为 $5$ 。 $998244353$ 的原根为 $3$ 。
最大公约数和最小公倍数
求 n 的正约数集合
复杂度是 $O({\sqrt {n}})$ 的。
求 1…n 中每个数的正约数的集合
求 $1…n$ 中每个数的正约数的集合，算法复杂度 $O(nlogn)$ ，总数也是这个级别的。
方法倍数法：类似于埃氏筛的思路，枚举倍数，如果能除开一定会被发现，并且因为每轮倍数不同，所以只发现一次。
一些结论
$gcd(F(n),F(m))=F(gcd(n,m))$
$gcd(a^{m}-1,a^{n}-1)=a^{gcd(n,m)}-1(a>1,n>0,m>0)$
更进一步，有：
$gcd(a^{m}-b^{m},a^{n}-b^{n})=a^{gcd(n,m)}-b^{gcd(n,m)}(gcd(a,b)=1)$
设 $G=gcd(C(n,1),C(n,2),…,C(n,n-1))$
1.若 $n$ 为素数， $G=n$ ，因为分母不含 $p$ ，分子有 $p$ 。
2.$n$ 非素且有只有一个素因子 $p$ ， $G=p$ ， $n=p^{a}$ ，显然分母幂次小于分子幂次，取 $C(n,p^{a-1})$ ，可以证明分子只比分母多一次，所以 $G=p$ 。
3.$n$ 有多个素因子， $G=1$ ，将 $n$ 做质因数分解，设 $p_{1}$ 的幂次是 $a_{1}$ ，取 $C(n,p_{1}^{a_{1}})$ ，可以证明没有 $p_{1}$ 的幂次。同理也有没有 $p_{i}$ 幂次的数，所以所有的最大公约数是 $1$ 。
$(n+1)lcm(C(n,0),C(n,1),…,C(n,n))=lcm(1,2,…,n+1)$
$\sum_{i=1}^{n}gcd(i,n) = \sum_{d|n}d{\phi ({\frac {n} {d}})}$
斐波那契数列
前缀和： $\sum_{i=1}^{n}f_{i}=f_{n+2}-1$ 数学归纳法。
奇数项前缀和： $\sum_{i=1}^{n}f_{2i-1}=f_{2n}$ 数学归纳法。
偶数项前缀和： $\sum_{i=1}^{n}f_{2i}=f_{2n+1}-1$ 数学归纳法。
平方前缀和： $\sum_{i=1}^{n}f_{i}^{2}=f_{n}f_{n+1}$ 数学归纳法
$f_{n+m}=f_{n-1}f_{m-1}+f_{n}f_{m}$
$f_{n}^{2}=(-1)^{n-1}+f_{n-1}f_{n+1}$
$f_{2n-1}=f_{n}^{2}-f_{n-2}^{2}$
$f_{n}={\frac {f_{n+2}+f_{n-2}} {3}}$
