基础数论
扩展欧几里得算法 $\mathbf{exgcd}$
首先介绍一下贝祖定理。若 $a,b$ 是整数，那么 $a\cdot x+b\cdot y=\gcd(a,b)$一定有解。如果需要判断 $a\cdot x+b\cdot y=c$ 有没有解，可以直接判断 $c|\gcd(a,b)$可以用欧几里得算法求 $\gcd(a,b)$。但如果需要求出一组解，我们就必须对欧几里得算法进行扩展。考虑边界，欧几里得算法结束的条件是$b=0,a=\gcd(a,b)$ ，此时可以得到一组解 $x=1,y=0$。再考虑回溯是处理，每层我们都已知 $\gcd(b,a\bmod b)$ ，并且有一组解$x1,y1$ 使得 $b\cdot x1+(a\bmod b)\cdot y1=gcd$ 。我们知道，$a\bmod b=a-\left\lfloor\frac{a}{b}\right\rfloor\cdot b$ 带入化简得$a\cdot y1+b\cdot (x1-\left\lfloor\frac{a}{b}\right\rfloor\cdot y1)=gcd$ 可以发现，$x=y1,y=x1-\left\lfloor\frac{a}{b}\right\rfloor\cdot y1$可以递归求解。时间复杂度为 $\Theta(\log_2 \max(a,b))$
乘法逆元 $\mathbf{inv}$
对于两个数 $a,p$ ，若有 $\gcd(a,p)=1$ ，那么一定
$\exists b\quad a\cdot b\equiv 1\pmod{p}$ 。此时称 $b$ 为 $a$ 在模 $p$
意义下的逆元，记做 $a^{-1}=b$ 。计算乘法逆元，有多种方法。
费马小定理
费马小定理的内容是若 $\gcd(a,p)=1$ 则有 $a^p\equiv a\pmod{p}$
将其变形，可得 $a\cdot a^{p-2}\equiv 1\pmod{p}$ 所以可以得到
$a^{-1}=a^{p-2}$ 可用快速幂求出。
扩展欧几里得
由定义可变形得到 $a\cdot a^{-1}=k\cdot p+1$ 移项可得 $a\cdot a^{-1}-k\cdot p=1$
与扩展欧几里得的标准形式一致。
线性递推计算
首先简单计算可得 $1^{-1}=1$ 。考虑对于 $\forall i$ ，如果 $i-1$
的逆元已经求出，可以线性求出。令 $p=k\cdot i+r$ ，则
$k=\left\lfloor\frac{p}{i}\right\rfloor,r=p \bmod i$ ，可得
$k\cdot i+r\equiv 0\pmod{p}$ 经过代入整理得
$i^{-1}\equiv-\left\lfloor\frac{p}{i}\right\rfloor\cdot (p \bmod i)^{-1}\pmod{p}$
得出线性递推式。时间复杂度为 $\Theta(n)$ 。
阶乘递推计算
由逆元的定义可得 $n!^{-1}\equiv \frac{1}{n!}\pmod{p}$ 左右同乘 $n$
，化简得 $n!^{-1}\cdot n\equiv (n-1)!^{-1}\pmod{p}$ 得到递推式
$n!^{-1}\equiv \frac{(n-1)!^{-1}}{n}\pmod{p}$
中国剩余定理 $\mathbf{crt}$
中国剩余定理主要是为了解一种特殊的同余方程组。形如 $\begin{cases}
x\equiv a_1\pmod{p_1}\\
x\equiv a_2\pmod{p_2}\\
\cdots \\
x\equiv a_n\pmod{p_n}
\end{cases}$ 的式子。同时，式子满足 $\forall i,\forall j,i\neq j$
都有 $\gcd(p_i,p_j)=1$ 。考虑暴力做法，可以得到答案为下式
$k_1\cdot \frac{p_1\cdot p_2\cdot \cdots \cdot p_n}{p_1}+k_2\cdot \frac{p_1\cdot p_2\cdot \cdots \cdot p_n}{p_2}+\cdots +k_n\cdot \frac{p_1\cdot p_2\cdot \cdots \cdot p_n}{p_n}$
且 $\forall i,i\leq n$ 满足
$k_i\cdot \frac{p_1\cdot p_2\cdot \cdots \cdot p_n}{p_i}\bmod p_i=a_i$ 。设
$m_i=\frac{p_1\cdot p_2\cdot \cdots \cdot p_n}{p_i}$ 那么 $k_i\cdot m_i\equiv a_i\pmod{p_i}$
此时可以用逆元来求解 $k_i$ 最后求出答案。时间复杂度为 $\Theta(1)$ 。
扩展中国剩余定理 $\mathbf{excrt}$
如果中国剩余定理中的 $p_i$ 不满足 $\forall i,\forall j,i\neq j$ 都有
$\gcd(p_i,p_j)=1$ ，就不能使用中国剩余定理求解。考虑两两合并，下面方程组
$\begin{cases}
x\equiv a_1\pmod{p_1}\\
x\equiv a_2\pmod{p_2}\\
\end{cases}$ 可以化成 $p_1\cdot y+a_i=p_2\cdot z+a_2$
这个东西可以用扩展欧几里得合并。每次两两合并得出答案。时间复杂度
$\Theta(n\cdot \log_2 n)$ 。
大步小步算法 $\mathbf{BSGS}$
$BSGS$ 算法的目的是求解形如 $a^b\equiv c\pmod{p}$ ，其中 $\gcd(a,p)=1$
的同余方程。首先将 $b$ 写成 $k\cdot x+r$ 的形式。代入原式，得
$a^{k\cdot x}\equiv c\cdot a^r\pmod{p}$ 首先求出 $b$ 在 $[0,x-1]$
范围内右式的值，并储存。然后枚举所有可能的 $a$
，计算出左式的值，然后查询。时间复杂度为 $\Theta(\max(x,p/x))$ 可得
$x=\sqrt{p}$ 是最优。时间复杂度 $\Theta(\sqrt{p})$ 。
扩展大步小步算法 $\mathbf{exBSGS}$
如果在求解形如 $a^b\equiv c\pmod{p}$ 的同余方程时 $\gcd(a,p)\neq 1$
我们不能用 $BSGS$
来求。这个时候我们就必须换一种方法。首先把方程改写为等式 $a^b+k\cdot p=c$
发现此时的 $c$ 必须要是 $\gcd(a,p)$
的倍数，否则无解。不断在等式两边同时除以 $gcd(a,p)$ 直到
$\gcd(a,\frac{c}{\gcd(a,p)})=1$ ，此时式子满足 $BSGS$ 的求解条件，用
$BSGS$ 求解。
卢卡斯定理 $\mathbf{Lucas}$
$Lucas$ 定理用于求 $C_n^m\bmod p$ 的值。由二项式定理可知 $C_n^m$ 即为
$(x+1)^n$ 中 $x^m$ 的系数。对于式子
$(x+1)^{n_0}\cdot (x^p+1)^{n_1}\cdot (x^{p^2}+1)^{n_2}\cdot \cdots \cdot (x^{p^n}+1)^{n_k}\pmod{p}$
$C_{n_0}^{m_0}$ 即为 $(x+1)^n_0$ 中 $x^{b_0}$ 的系数， $C_{n_k}^{m_k}$
即为 $(x^{p^k}+1)^{n_k}$ 中 $x^{b_k\cdot p^k}$ 的系数，同理可得其余。因为
$\prod_{i=0}^k C_{n_i}^{m_i}\cdot x^{m_i\cdot p^i}=C_n^m\cdot x^m$ 所以可得
$C_n^m=\prod_{i=0}^k C_{n_i}^{m_i}$ 时间复杂度为 $\Theta(p\cdot \log_p n)$
。
素数合数
枚举判断
思路很简单，枚举 $[2,\left\lfloor\sqrt{n}\right\rfloor]$
范围内所有的数，判断是否是 $n$ 的因数。时间复杂度为 $\Theta(\sqrt{n})$
。
埃氏筛
埃氏筛的思想很简单，从 $2$
开始向后扫描，如果这个数是不是合数，那么把它的倍数全部标记为合数。时间复杂度为
$\Theta(n\cdot log_2 n)$ 。
线性筛
考虑优化埃氏筛。发现每个数都被它所有的质因数打上标记。可以通过使每个数都只被它最小的质因子筛去。将每个数的质数倍的数标记为合数（无论其本身是不是合数），这样可以保证每个数只会被自己最小的质因子筛去。
$\mathbf{Miller-Rabin}$
当我们需要判断一个数是否是质数时，我们需要 $\Theta(\sqrt{n})$
的时间判断。当这个数较大的时候，我们就不能使用枚举。考虑使用费马小定理。但当
$\gcd(a,b)=1$ 且 $a^p\equiv a\pmod{p}$ 时，不能得出 $p$
是质数的结论。这个时候我们引入二次探测。如果 $p$ 为质数，且 $0<x<p$
则方程 $x^2\equiv 1\pmod{p}$ 的解为 $x=1$ 或 $x=p-1$ 。 $Miller-Rabin$
判断 $n$ 是否为质数的流程为：首先判断 $0,1,2$
和偶数。先随机取一个较小的质数 $p$ ，设 $s,t$ 满足 $2^s\cdot t=n-1$ 。算出
$p^t$ ，进行 $s$
次二次探测，每次进行平方，最后用费马小定理判断。多次取不同的 $p$
进行判断，如果全部通过，那么 $n$ 大概率是质数。算法时间复杂度为
$\Theta(p\cdot \log_2^3 n)$
函数
数论函数
数论函数是指这样一类函数：其定义域是正整数，值域是一个数集。定义两个数论函数的加法，为逐项相加，即
$(\mathbf{f+g})(n)=\mathbf{f}(n)+\mathbf{g}(n)$
。数乘，即一个数乘到一个数论函数上，定义为这个数和每一项都相乘，即
$(x\cdot \mathbf{f})(n)=x\cdot \mathbf{f}(n)$ 。
狄利克雷卷积
狄利克雷卷积是数论函数的一个运算。设 $\mathbf{h=f\times g}$ ，那么有
$\mathbf{h}(n)=\sum_{i|n} \mathbf{f}(i)\cdot \mathbf{g}(\frac{n}{i})$
它拥有以下性质：
- $\mathbf{f\times g=g\times f}$
- $\mathbf{(f\times g)\times h=f\times (g\times h)}$
- $\mathbf{(f+g)\times h=f\times h+g\times h}$
- $(x\times \mathbf{f})\times \mathbf{g}=x\times (\mathbf{f\times g})$
- $\epsilon \times \mathbf{f}=\mathbf{f}$
欧拉函数
欧拉函数 $\phi(n)$ 是小于或等于 $n$ 的正整数中与 $n$
互质的数的数目。通式为 $\varphi(x)=x\cdot \prod_{i=1}^n (1-\frac{1}{p_i})$
其中 $p_1,p_2\cdots p_n$ 为 $x$
的质因子。处理可以用定义求解，也可以用埃氏筛和线性筛求解。
莫比乌斯函数
莫比乌斯函数的通式为 $\mu (n)=
\begin{cases}
1\quad n=1\\
(-1)^k\quad p_1\times p_2\times \cdots \times p_n\\
0\quad else
\end{cases}$ 莫比乌斯函数主要用于容斥原理。