一.定义
\(\varphi(n)=\sum\limits_{i=1}^{n}[\gcd(i,n)=1]\)，即 \(n\) 以内与 \(n\) 互质的数的个数，叫做欧拉函数，念做 /faɪ/。
\(\mu(n)=\begin{cases}1 &n=1\\0 &\exists i\in[1,m],k_i>1 \\(-1)^m & \forall i \in[1,m],k_i=1 \end{cases}\)，记 \(n=\prod\limits_{i=1}^{m}p_i^{k_i}\)，叫做莫比乌斯函数，念做 /mju:/。
下面的表从此博客copy来：
| 函数名称 | 符号 | 定义 | 积性 | 卷积 |
|---|---|---|---|---|
| 恒等函数 | \(I(n)\) 或 \(1(n)\) | \(1\) | 完全积性函数 | |
| 元函数 | \(\varepsilon(n)\) 或 \(e(n)\) | \([n=1]\) | 完全积性函数 | \(\varepsilon=\mu*1\) |
| 单位函数 | \(id(n)\) | \(n\) | 完全积性函数 | \(id=\varphi*1\) |
| 幂函数 | \(id^x(n)\) | \(n^x\) | 完全积性函数 | |
| 莫比乌斯函数 | \(\mu(n)\) | 见上 | 积性函数 | |
| 欧拉函数 | \(\varphi(n)\) | 见上 | 积性函数 | \(\varphi=\mu*id\) |
| 约数个数函数 | \(d(n)\) 或 \(\sigma_0(n)\) | n的约数个数 | 积性函数 | \(d=1*1\) |
| 约数和函数 | \(\sigma(n)\) | n的约数和 | 积性函数 | \(σ=id*1\) |
| 除数函数 | \(\sigma^k(n)\) | n的约数k次方和 | 积性函数 | \(σ^k=id^k*1\) |
注：\(\varepsilon\) 念做 /'epsɪlɒn/，\(\sigma\) 念做 /'sɪɡmə/。
二.定理
费马小定理&欧拉定理
-
若 \(p\) 为质数且 \(a\not\equiv 0\pmod p\)，则 \(a^{p-1}\equiv 1\pmod p\).
-
若 \(\gcd(a,m)=1\)，则 \(a^{\varphi(m)}\equiv 1\pmod m\).
\(\varphi\) 相关
-
若 \(p\) 为质数，则 \(\varphi(p)=p-1\).
-
若 \(p\) 为质数且 \(k\ge1\)，则 \(\varphi(p^k)=p^k-p^{k-1}\).
-
若 \(\gcd(n,m)=1\)，则 \(\varphi(nm)=\varphi(n)\varphi(m)\).
-
设 \(n=\prod\limits_{i=1}^{m}p_i^{k_i}\)，则 \(\varphi(n)=n\times\prod\limits_{i=1}^{m}\frac{p_i-1}{p_i}\).
\(\mu\) 相关
- \(\sum\limits_{d|n}\mu(d)=[n=1]\)，同理 \([gcd(i,j)=1]=\sum\limits_{d|gcd(i,j)}\mu(d)\).
三.算法
1.欧几里得相关
求 \(\gcd\)
\[\gcd(a,b)=\begin{cases}a & b=0 \\ \gcd(b,a\bmod b) & b\not=0\end{cases} \]利用这个东西递归计算即可。
扩展欧几里得（exgcd）求解同余方程
- 记 \(g=\gcd(a,b)\)，求解下列方程：\(ax+by=g\)
设计函数 exgcd(ll a,ll b,ll &x,ll &y)。
当 \(b=0\) 时，我们解此时的方程 \(a_0x+b_0y=g=a_0\)，只需令 \(x=1,y=0\) 即可。
若已经知道了 \(bx+(a\bmod b)y=g\) 的一组解 \(x_0,y_0\)，如何借出方程 \(ax+by=g\) 的一组解？
\[\begin{aligned}bx_0+(a\bmod b)y_0&=bx_0+(a-\lfloor \frac{a}{b} \rfloor \cdot b)y_0 \\&=bx_0+ay_0- \lfloor \frac{a}{b} \rfloor \cdot by_0 \\&=a(y_0)+b(x_0-\lfloor \frac{a}{b} \rfloor \cdot y_0)\end{aligned}\]于是我们就得到了一组解 \(x=y_0,y=x_0-\lfloor \frac{a}{b} \rfloor \cdot y_0\)，不停地向上回溯即可解出原方程的解。
代码：
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=1,y=0;return a; }
ll d=exgcd(b,a%b,x,y);
ll z=x; x=y; y=z-y*(a/b);//妈妈生的！！a/b要带括号！！！
return d;
}
-
方程 \(ax+by=c\) 当且仅当 \(\gcd(a,b)\,|\,c\) 时有解。
-
解同余方程 \(ax\equiv b\pmod m\) 时，只需解出 \(ax-my=b\) 的一组解即可。当且仅当 \(\gcd(a,m)\,|\,b\) 时有解。
//解同余方程 ax≡b(mod m)
ll TYFC(ll a,ll b,ll m){
ll x,y,mm;
ll G=exgcd(a,m,x,y);
if(b%G) return -1;
x*=b/G;mm=m/G;
return (x%mm+mm)%mm;
}
类欧几里得算法
单独写一篇博客了，在这里。
2.素数相关
（一）筛法
①埃氏筛
\(\color{red}\text{咕咕咕咕咕}\)
②线性筛
\(\color{red}\text{咕咕咕咕咕}\)
？？？.推式子技巧
1. 总结性式子
（一）
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=1] = \sum\limits_{i=1}^{n} \Big(2\cdot \sum\limits_{j=1}^{i}[\gcd(i,j)=1]\Big) -1 =\sum\limits_{i=1}^{n}\Big( 2\varphi(i) \Big)-1 \]\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd(i,j) =\sum\limits_{d=1}^{n}\Big(d\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i,j)=1]\Big) =\sum\limits_{d=1}^{n}\Bigg(d\cdot\Big(\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}( 2\varphi{\scriptstyle(i)} )-1\Big)\Bigg) \]详细解释在数论习题这篇博客中P2568 GCD这个题里提到。
（二）
\(\color{red}\text{上述两个式子，把 } j \text{ 的上界换成 }m\)
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=1] =\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|\gcd(i,j)}\mu(d) =\sum\limits_{d=1}^{\min(n,m)} \Big(\mu(d) \cdot (\sum\limits_{i=1}^{n}[d|i]) \cdot (\sum\limits_{j=1}^{m} [d|j])\Big) =\sum\limits_{d=1}^{\min(n,m)} \Big(\mu(d) \lfloor\frac{n}{d}\rfloor \lfloor\frac{m}{d}\rfloor\Big) \]借助了莫反，详细解释在数论习题这篇博客中P2522 [HAOI2011] Problem b这个题里提到。
\[\begin{aligned} \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j) &=\sum\limits_{d=1}^{\min(n,m)}d\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{i=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1] \\&=\sum\limits_{d=1}^{\min(n,m)} \Bigg( d\cdot \sum\limits_{k=1}^{\min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)} \Big(\mu(k) \lfloor\frac{\lfloor\frac{n}{d}\rfloor}{k}\rfloor \lfloor\frac{\lfloor\frac{m}{d}\rfloor}{k}\rfloor \Big) \Bigg) \\&=\sum\limits_{d=1}^{\min(n,m)} \Bigg( d\cdot \sum\limits_{k=1}^{\min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)} \Big(\mu(k) \lfloor\frac{n}{dk}\rfloor \lfloor\frac{m}{dk}\rfloor \Big) \Bigg) \end{aligned}\]
到这里，这个式子已经可以两次数论分块做出来了，但还有优化空间：
注意到：\(dk\le\min(n,m)\)，而 \(\lfloor\frac{n}{dk}\rfloor \lfloor\frac{m}{dk}\rfloor\) 同时和 \(d\,,\,k\) 相关，也只和 \(dk\) 相关，于是可以考虑枚举 \(T=dk\)：
\[\text{原式}=\sum\limits_{T=1}^{\min(n,m)}\lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor\sum\limits_{k|T}\mu(k)\frac{T}{k} \]发现 \(\sum\limits_{k|T}\mu(k)\frac{T}{k}\) 就是 \(\mu * id=\varphi\)，所以：
\[\text{原式}=\sum\limits_{T=1}^{\min(n,m)}\lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor \varphi(T) \]一次数论分块即可。
2. 其他小技巧
-
\(\sum\limits_{d|n}\mu(d)=[n=1]\)，同理 \([gcd(i,j)=1]=\sum\limits_{d|gcd(i,j)}\mu(d)\).
-
\(\sum\limits_{i=1}^{n} f(i)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{f(i)}1 =\sum\limits_{j=1}^{f(n)}\sum\limits_{i=1}^{n}[j\le f(i)]\)，来源于P5170 【模板】类欧几里得算法
-
\(nm=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=1]\min(\lfloor\frac{n}{i}\rfloor,\lfloor\frac{m}{i}\rfloor)\)，无意间发现的，不知道有什么用。
-
\(d(nm)=\sum\limits_{i|n}\sum\limits_{j|m}[\gcd(i,j)=1]\)