数论
1. 最大公约数
最大公约数
欧几里得定理 / 辗转相除法：$\text{gcd}(a,b)=\text{gcd}(b,a\mod b)$
更相减损术（适用于大数计算）：$\text{gcd}(a,b)=\text{gcd}(a-b,b)$
其需要结合 $\text{stein}$ 算法的优化：
若 $2\mid a,\space 2\mid b$，则 $\text{gcd}(a,b)=2\times \text{gcd}(a/2,b/2)$
若仅有 $2\mid a$，则 $\text{gcd}(a,b)=\text{gcd}(a/2,b)$
最小公倍数
$\text{gcd}(a,b)\times \text{lcm}(a,b)=a\times b$
扩展欧几里得
(将最大公约数与线性组合互相转化)
求 $ax+by=\text{gcd}(a,b)$ 的可行解
过程：
令 $ax_1+by_1=\text{gcd}(a,b),bx_2+(a\mod b)y_2=\text{gcd}(b,a\mod b)$
代入 $a\mod b=a-\lfloor\frac{a}{b}\rfloor\times b$，解得 $x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2$
不断递归直到 $b=0$，此时 $x=1,y=0$，向上传递。
P1292 倒酒
P2421 [NOI2002] 荒岛野人
2. 欧拉函数
定义：$\varphi(n)=[1,n]$ 中与 $n$ 互质的数的个数
- $n$ 为质数时有 $\varphi(n)=n-1$
性质:
欧拉函数为积性函数，即当 $\text{gcd}(a,b)=1$ 时，$\varphi(a)\times \varphi(b)=\varphi(ab)$
- 结合素数筛线性预处理欧拉函数
- $n=\sum_{d\mid n}\varphi(d)$
欧拉函数常常用于化简一列最大公约数的和：
$\text{gcd}(a,b)=\sum_{d\mid\text{gcd}(a,b)}\varphi(d)=\sum[d\mid a][d\mid b]\varphi(d)$
P2158 [SDOI2008] 仪仗队
P2398 GCD SUM
$\sum\limits_1^n i[\text{gcd}(i,n)=1]=\frac{n}{2}\varphi(n)$
- 若 $\text{gcd}(i,n)=1$，则 $\text{gcd}(n-i,n)=1$
P1891 疯狂 LCM
欧拉定理
$\text{gcd}(a,m)=1$，有 $a^{\varphi(m)}\equiv 1\mod m$
- $m$ 为质数时即 $a^{m-1}\equiv1\mod m$（费马小定理）
证明
首先引入 $m$ 的缩剩余系$*^{[1]}$。
设这个缩剩余系为：$R={r_1,r_2,…,r_{\varphi(m)}}$，满足 $1\leq r_i<m$。
取 $a$ 满足 $\text{gcd}(a,m)=1$，则 $aR={ar_1,ar_2,…,ar_{\varphi(m)}}$ 也为缩剩余系。
易知 $\text{gcd}(ar_i,n)=1$。
假设 $ar_i\equiv ar_j\mod m$，那么 $n\mid a(r_i-r_j)$，不成立。
从而有：$\prod r_i\equiv \prod (ar_i)\mod m$。
$\Rightarrow(a^{\varphi(m)}-1)\prod r_i\equiv 0\mod m$。
只能有 $a^{\varphi(m)}\equiv1\mod m$。
扩展欧拉定理
$$
a^k\equiv
\begin{cases}
a^{k\mod\varphi(m)} & \text{gcd}(a,m)=1 \\
a^k & \text{gcd}(a,m)\not=1,k<\varphi(m) \\
a^{(k\mod\varphi(m))+\varphi(m)} & \text{gcd}(a,m)\not=1,k\geq\varphi(m)
\end{cases}
\mod m
$$
P5091 【模板】扩展欧拉定理
3. 线性同余方程
P2613 【模板】有理数取余
形如 $ax\equiv b\mod n$，找 $x\in[0,n-1]$ 的特解。
1. 逆元法：
若 $\text{gcd}(a,n)=1$，则有唯一解 $x\equiv b\cdot a^{-1} \mod n$
若 $\text{gcd}(a,n)=d>1$
$d\nmid b$，无解
$d\mid b$，将 $a,b,n$ 都除以 $d$，有 $a’x\equiv b’\mod n’$，此时 $\text{gcd}(a’,n’)=1$
2. 不定方程求解
裴蜀定理：若 $a\times b\not=0$，则 $\text{gcd}(a,b)\mid ax+by$ 恒成立，且存在 $x,y$ 使得 $\text{gcd}(a,b)=ax+by$（可以推广到多个数）
- P4549 【模板】裴蜀定理
原式转化为 $ax+ny=b$，有解条件为 $\text{gcd}(a,n)\mid b$，从特解到通解易求。
4. 逆元
P1082 [NOIP 2012 提高组] 同余方程
求解 $ax\equiv1\mod p$
1. 扩展欧几里得算法
上式等价于 $ax+py=1$
2. 快速幂
定理：只要 $p$ 为素数，即有 $a^m\equiv a \mod p$
费马小定理：$p$ 为素数，且 $p\nmid a$，则 $a^{m-1}\equiv 1\mod p$
扩展欧拉定理
多个数求逆元：略
线性预处理逆元
- $p=\lfloor\frac{p}{i}\rfloor i+(p\mod i)$
- $\Rightarrow 0\equiv \lfloor\frac{p}{i}\rfloor i+(p\mod i)\mod p$
- $\Rightarrow i^{-1}=-\lfloor\frac{p}{i}\rfloor(p\mod i)^{-1}$
易知 $p\mod i<i$，从 $1$ 开始递推即可。
P3811 【模板】模意义下的乘法逆元
5. 阶 & 原根
（下文中默认 $a\perp m$）
杂谈
- 系 & （完全）剩余系 & 缩剩余系
数学中的“系”通常可以理解为集合。
“（完全）剩余系”指的是从每个同余类中选出任意一个元素作代表，构成的大小为 $m$ 的结合。
“缩剩余系”则是只考虑与 $m$ 互质的同余类，集合大小为 $\varphi(m)$。参考 $\varphi(m)$ 的定义，$0$ 是不被考虑的。