数论基础
导读：快速幂取模、欧式筛法、裴蜀定理（贝祖定理）、威尔逊定理、费马定理、（扩展）中国剩余定理。
快速幂取模
求\(a^b \% p\)我们有时间复杂度\(O(b)\)的办法。但数据规模放大时，我们的显示界面难免会出现一个老熟人 TLE，我们需要更快的方法。
根据初中数学，\(a^b\)可以化为\((a^2)^\frac{b}{2}*a^{b\%2}\)，也就是我们把底数\(a\)平方一次，指数\(b\)就缩小了一半（指数\(b\)是奇数时答案要多乘一个这时的\(a\)，因为\(b\)除不尽\(2\)），那么我们使\(a=a^2\)后再进行上述操作，便可使\(b\)快速缩小，在\(O(log_2 b)\)的时间求解。
CODE
ll ksm(ll a, ll b, ll p) {
ll ans = 1;
while (b) {
if (b & 1)//相当于b%2==1，即b为奇数的情况
ans *= a;
a *= a;//将a平方
a %= p;
ans %= p;
b /= 2;
}
return ans;
}
欧式筛法
埃式筛法已经可以做到很优秀的时间复杂度\(O(nlogn)\)，但当\(n\)上升到\(10^7\)以上（参考惨痛的GDKOI2023普及组Day1的T1），我们就需要更快的做法。
先将\(2\)加入质数集合\(P\)，然后从2开始枚举倍数\(a\)，将倍数和我们的每一个集合\(P\)中的每一个质数相乘并打上标记。当枚举\(a\)时，\(a\)没有打上标记则\(a\)为质数，将\(a\)加入质数集合\(P\)。
优化。枚举集合\(P\)中的数时，如果\(a\)是\(p_i\)的倍数，则可以退出枚举集合\(P\)的循环。因为后续质数\(p_{i'}*a\)也一定是\(p_i\)的倍数，当\(a\)变大过程中，必有\(p_i*a'=p_{i'}*a\)（\(p_{i'}*a\)是\(p_i\)的一个倍数）。这样做可以保证每一个质数被他最小的质因子打上一次标记。
显而易见时间复杂度为\(O(n)\)
for (int i = 2; i <= n - 1; i++)
{
if (vis[i] == 0)
prim[++cnt] = i;
for (int j = 1; j <= cnt; j++)
{
if (prim[j] * i > n)
break;
vis[i * prim[j]] = 1;
if (i % prim[j] == 0)
break;
}
}
裴蜀定理（贝祖定理）
如果\(a\)和\(b\)的最大公约数为\(d\)且\(d\)整除\(c\)，那么有\(ax+by=c\)
证明：
令\(a'=a/d\)，\(b'=b/d\)，可以证明\(a'x+b'y=1\)。
则
\[a'x-1=-b'y\\ \frac{a'x-1}{b}=-y\\ \frac{a'x}{b}=-y余1\\ \]即
\[a'x \% b=1 \]引理一：如果\(a\)和\(b\)为正整数且\(gcd(a,b)=1\)，则不存在整数\(k\)(\(0 \lt k \lt b\))使得\(k*a \% b=0\)。
证明：用反证法，因为\(a*k \% b=0\)，所以\(a*k\)包含了\(b\)中所有质因子。因为\(gcd(a,b)=1\)，所以\(k\)为\(b\)的倍数。但\(k \lt b\)，所以\(k\)不为\(b\)的倍数。产生了矛盾，得证。
推论：如果\(a,b\)为正整数，\(gcd(a,b)=1\)。\(0*a,1*a,2*a,...,(b-1)*a\)模\(b\)各不相同。
证明：用反证法，若\(i*a \% b=j*a \% b\)则\((i-j)*a \% b=0\)。因为\(0 \lt i,j \lt b\)，设\(j \lt i\)，则\(0 \lt i-j \lt b\)，与引理一矛盾，得证。
引理二：如果\(gcd(a,b)=1\)，则有一个整数\(k\)，使得\(k*a \% b=1\)
证明：根据推论\(k*a \% b\)的结果只能是集合\({0,1,...,b-1}\)中的数。又因为集合中的数个不相等且有\(b\)个，其中肯定有\(1\)个为\(1\)。
根据引理二，裴蜀定理得证。
威尔逊定理
\((p-1)! \equiv -1 \mod p\)，当且仅当\(p\)为质数。
证明：
先证明充分性：
即\(p\)为质数\(\rightarrow (p - 1)! \equiv -1 \mod p\)
设\(0 \lt i \lt p\)，由裴蜀定理引理2可知\(i\)的逆元（\(1 \lt x \lt p\)）具有唯一性，现在来讨论\(i^2 \equiv 1 \mod p\)。
由
\[i^2 \% p = 1 \]得
\[i^2 - k*p = 1 \]移项得：
\[i^2 - 1 = k*p \]根据小学的平方差公式得：
由于\(p\)是质数，那么\(i + 1\)为\(p\)的质数或\(i - 1\)为\(p\)的质数，且有\(0 \lt i \lt p\)，得
\[i + 1 = p 或 i - 1 = 0 \]即
\[i = p - 1 或 i = 1 \]所以说对于\(1 \lt i \lt p - 1\)都有一个不等于自己的数字相乘模\(p\)等于\(1\)，那么由模的基本性质可得\(1 * 2 * 3 * … * (p - 1) = 1 * (p - 1) \equiv p - 1 \mod p\)。
即\(p - 1 \equiv -1 \mod p\)。
充分性得证。
再证明必要性：
即\((p - 1)! \equiv -1 \mod p \rightarrow\)\(p\)为质数。
即证\(p\)不为质数\(\rightarrow (p - 1)! \equiv i (i \neq 1) \mod p\)
如果\(p\)不是质数那么\(p\)的每一个因子都小于\(p\)，设\(i(1 \lt i \lt p)\)为\(p\)的因数。
若有\(i * i \neq p\)，那么\((p - 1)! \equiv 0 \mod p\)。
若有\(i * i = p\)，那么\((p - 1)! \mod p\)必为\(i\)的倍数。
必要性得证。
费马定理
若\(p\)为质数，且\(a \% p \neq 0\)，那么\(a^{p-1} \equiv 1 \mod p\)。
证明：
\[(a * 1) * (a * 2) * (a * 3) * … * (p - 1) \% p = a ^ {p - 1} * (p - 1)! \% p \]又因为：
\(p\)为质数，根据裴蜀定理推论，得\((a * 1) \% p,(a * 2) \% p,…,(a * (p - 1)) \% p\)结果互不相等，且\(1\lt a*i\%p \lt p\)，所以：
由我们上面的结论可知：
\[(p - 1)! \% p = a ^ {p - 1} * (p - 1)! \% p \]由威尔逊定理得
\[(p - 1) \% p = a ^ {p - 1} * (p - 1) \% p \]因为\(p - 1\)与\(p\)互质，等式两边同时除以\(p - 1\)，得
\[1 \% p = a ^ {p - 1} \% p \]费马定理得证。
该定理多用于求一个数关于质数的逆元。
中国剩余定理(CRT)
扩展欧几里得后面再补。
方程思想是数学中很麻烦重要的思想，如果我们有一些同余的等式，那么我们可以列出如下的同余方程。
CRT是解决这种方程组在\(r_1,r_2,\cdots,r_n\)互质的模线性方程组。
因为\(r_1,r_2,\cdots,r_n\)互质，令\(A_i=r_1*r_2*\cdots*r_{i-1}*r{i+1}*r{i+2}*\cdots*r_n\)，即\(A_i=\prod\limits_{j \neq i} r_j\)，则\(A_i\)与\(r_i\)互质。
根据裴蜀定理引理2，存在\(c_i\)使得\(c_i*A_i \equiv 1 \mod r_i\)，则设\(x_i=c_i*A_i*b_i\)，易得\(x_i \equiv b_i \mod r_i\)，而\(A_i\)可以被其他的\(r_i\)整除，所以\(x_i \equiv 0 \mod r_j \quad(j \neq i)\)。
那么易得\((x_i+x_j) \equiv b_i \mod r_i\)且\((x_i+x_j) \equiv b_j \mod r_j\)。
易证\(\sum\limits_{i=1}^{n}x_i\)满足每一个方程，那么\(x=\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}A_i*c_i*b_i\)
对于\(x\)，如果加上所有\(r_i\)的公倍数，那么\(x\)依然满足条件。
即通解为\(x=\sum\limits_{i=1}^{n}A_i*c_i*b_i+p*\prod\limits_{i=1}^{n}r_i\)
其中\(p\)为任意整数。