0. 前置知识
0.1 常用数学标识
- 若 \(a\) 与 \(b\) 模 \(p\) 同余，则写成 \(a\equiv b\pmod p\)。
- 完全剩余系：\((a_1,a_2,...,a_{n-1})\) 模 \(n\) 两两不同，则称 \((a_1,a_2,...,a_{n-1}))\) 为模 \(n\) 的 完全剩余系。
0.2 二项式定理
\[(a+b)^n=\binom{n}{0}a^n+\binom{n}{1}a^{n-1}+...+\binom{n}{n}b^n \]特殊地，对于 \(a=x,b=1\) 而言，有：
\[(x+1)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i} \]0.3 费马小定理
若 \(p\) 为素数且 \(a,b\) 互素（即 \(\gcd(a,p)=1\)），则 \(a^{p-1}\equiv 1\pmod p\)。
另一种形式：\(a^p\equiv a\pmod p\)。
证明1（数学归纳法）：
显然有 \(1^p\equiv 1\pmod p\)，下面假设已知 \(a^p\equiv a\pmod p\)，则由二项式定理知：
\[(a+1)^p=a^p+\binom{p}{1}a^{p-1}+...+\binom{p}{p-1}a+1 \]显然对于所有 \(1\leq k\leq q-1\)，有 \(\binom{p}{k}\equiv 0\pmod p\)，那么由上式可得 \((a+1)^p\equiv a^p+1\pmod p\)，所以 \((a+1)^p\equiv a+1\)。
证法2（神仙证法）：
构造序列 \((x_1,x_2,...,x_{p-1})\) 满足 \(x_i=i\)，则 \(\gcd(x_i,p)=1\)。
又由于 \(\gcd(a,p)=1\)，所以 \(\gcd(x_i\cdot a,p)=1\)，那么因为每个 \(x_i\cdot a\) 各不相同，则必然是 \((1,2,...,p-1)\) 的某种排列。
\[(p-1)!\equiv a\cdot x_1\cdot a\cdot x_2\cdot...\cdot a\cdot x_{p-1}\pmod p\\ (p-1)!\equiv a^{p-1}\cdot (p-1)!\pmod p \]所以得证 \(a^{p-1}\equiv 1\pmod p\)。
注意点：
- 仅适用于 \(p\) 为素数且 \(\gcd(a,p)=1\) 的情况。
技巧：
- 可用于求 \(p\) 为素数的乘法逆元。
0.4 模意义下的乘法逆元
此处仅讨论 \(p\) 为素数情况，其它请移步扩展欧几里得部分。
当 \(p\) 为素数时，根据费马小定理 \(a^{-1}\equiv a^{p-2}\pmod p\)，可以用快速幂快速求出。
技巧：
- 线性求逆元：设 \(p=ki+r(0\leq r<i)\)，则 \(ki+r\equiv 0\pmod p\)。
两边除以 \(ir\) 得 \(i^{-1}=-kr^{-1}=-\lfloor\frac{p}{i}\rfloor^{-1}\pmod p\)
inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=(p-p/i)*inv[p%i]%p;
0.5 积性函数
定义：若函数 \(f\) 为积性函数，则必须满足对于任何 \(\gcd(a,b)=1\)，有 \(f(ab)=f(a)\cdot f(b)\)。
完全积性函数定义为对于所有 \((a,b)\)，都有 \(f(ab)=f(a)\cdot f(b)\)。
常见积性函数有 \(\varphi\)（欧拉函数），\(\mu\)（莫比乌斯函数）等。
技巧：
- 积性函数可以用来做各种各样的筛法。
1. 欧拉函数
感觉欧拉函数 OI 中还挺常用的？
1.1 定义与性质
定义：欧拉函数 \(\varphi(n)\) 表示 \(1\text{ ~ }n\) 中与 \(n\) 互素的数的个数。
性质1：欧拉函数为积性函数。
证明：设与 \(a\) 互素的数为 \((a_1,...,a_{\varphi(a)})\)，则在 \(1\text{ ~ }ab\) 范围内与 \(a\) 互素的数可以写成 \(ia+a_j(0\leq i<b,1\leq j\leq \varphi(a))\)。
因为 \(\gcd(a,b)=1\)，所以 \(ia\) 模 \(b\) 构成完全剩余系。
所以显然 \(\varphi(ab)=\varphi(a)\cdot\varphi(b)\)。
性质2（欧拉反演）：\(n=\sum_{d|n}\varphi(d)\)。
这个好像直接冲狄利克雷卷积？
大概证明如下：
\[\sum_{d|n}\sum_{i=1}^n[\gcd(i,n)=d]=\sum_{i=1}^n\varphi(\frac{n}{d})=\sum_{i=1}^n\varphi(i) \]性质3：当 \(n>2\) 时，有 \(2|\varphi(n)\)
感性证明就是两两配对。
性质4：若 \(p\) 为质数且 \(p|n\)，则：
\[\varphi(p)=\begin{cases} p\cdot \varphi(\frac{n}{p}) & p^2|n\\ (p-1)\cdot \varphi(\frac{n}{p}) & \text{otherwise} \end{cases} \]
证明：
引理1：若 \(p\) 是质数，则 \(\varphi(p^k)=(p-1)\cdot p^{k-1}=p^k\cdot \frac{p-1}{p}\)
这个引理的证明就是因为 \(p\) 为质数，则所有和 \(p\) 不互质的都是 \(p\) 的倍数，所以 \(\varphi(p^k)=p^k-p^{k-1}\)。
也就是 \(\varphi(p^k)=p^k\cdot \frac{p-1}{p}\)。
引理2：若 \(p\) 是质数，则 \(\varphi(p)=p-1\)。
因为对于所有 \(1\leq i<p\)，\(\gcd(i,p)=1\)，得证。
引理3：设 \(n\) 的标准分解为 \(\prod_{i=1}^kp_i^{c_i}\)，则有 \(\varphi(n)=n\cdot\prod_{i=1}^k\frac{p_i-1}{p_i}\)。
由引理1和性质1得：
\[\varphi(n)=\prod_{i=1}^k\varphi(p_i^{k_i})=\prod_{i=1}^kp_i^{k_i}\cdot\frac{p_i-1}{p_i}=n\cdot\prod_{i=1}^k\frac{p_i-1}{p_i} \]引理4：若 \(a|b\)，则 \(\varphi(ab)=a\cdot\varphi(b)\)。
由引理3且 \(a|b\) 得 \(\varphi(ab)=ab\cdot\prod_{i=1}^k\frac{p_i-1}{p_i},\varphi(b)=\prod_{i=1}^k\frac{p_i-1}{p_i}\)，得证。
此时由引理可推得原性质。