1.定义
- $\epsilon(n)=\begin{cases} 1& n=1 \\ 0& n >1 \end{cases}$
- $I(n)=1$
- $id(n)=n$
- $d(n)$因子个数
- $\sigma(n)$因数和
- $\mu (n)$莫比乌斯函数
- $\varphi (n)$欧拉函数
2.狄利克雷卷积
- $h(n)=\sum_{d|n}\space f(d)g(\frac{n}{d})$
- $h=f*g$
-
性质：
- 交换律$(f∗g=g∗f)$；
- 结合律$((f∗g)∗h=f∗(g∗h))$；
- 分配律$((f+g)∗h=f∗h+g∗h)$；
- 举个例子，对于交换律，我们看狄利克雷卷积的式子，实质上就是$n$的每一个约数带入$f$中的值，乘上与之对应的约数在gg中的值。
- 常见的（加深理解）：
- $d=I*I$
- $\sigma=id*I$
- $\varphi=\mu*id$
3.莫比乌斯函数：
(1)$\sum_{d|n}\mu(d)=\begin{cases}1& \text{n=1}\\ 0& \text{n>1} \end{cases}= \epsilon(n)$,即$\mu*I=\epsilon$
- 对于 $n=1$，等式显然成立。
- 设 $n> 1$ 并写 $n=p_1^{a_1}…p_k^{a_k}$ ，在 $\sum_{d|n}\mu{(d)}$ 中非零的项仅来自于 $d=1$ 与 $n$ 的约数是不同素数的乘积，即
- $\sum_{d|n}\mu{(d)} \\ = \mu(1)+\mu(p_1)+…+\mu(p_k)+\mu(p_1p_k)+…+\mu(p_{k-1}p_k)+…+\mu(p_1p_2…p_k) \\ =1+\binom{k}{1}(-1)+\binom{k}{2}(-1)^2+…+\binom{k}{k}(-1)^k \\=0$
(2)$\sum_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}$
- 证明：
- 首先$\sum_{d|n}\varphi(d)=n$
- 即$\varphi*I=id$
- 所以$\varphi*I*\mu=id*\mu$
- 所以$\varphi*\epsilon=id*\mu$
- 所以$\varphi(n)=\sum_{d|n}\mu(d)*\frac{n}{d}$
- 再把两边同除以n
- $\frac{\varphi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}$
(3)莫比乌斯反演
- 定义：$F(n)$和$f(n)$是定义在非负整数集合上的两个函数，并且满足
$F(n)=\sum_{d|n}f(d)$
- 那么有
$f(n)=\sum\mu(d) F(\frac{n}{d})$
- 这个定理称之为莫比乌斯反演
- 大致证明：
- $F(n)=\sum_{d|n}f(d)$
- 即$F=f*I$
- 然后都卷上$\mu$
- $F*\mu=f*I*\mu$
- 因为狄利克雷卷积具有交换律和结合律，又因为$\mu*I=\epsilon$
- 所以$f*(I*\mu)=f*\epsilon=f$，所以$f=\mu*F$
- 带回狄利克雷卷积得到原式
- 对于莫比乌斯反演，还有一种常用的式子：
$F(n)=\sum_{n|d}f(d)$
- 有
$f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$
- 大致证明：
- $\sum_{n|d}\mu(\frac{d}{n})F(d)$
- $=\sum_{n|d}\mu(\frac{d}{n})\sum_{d|x}f(x)$
- $=\sum_{n|x}f(x) \sum_{n|d且d|x} \mu(\frac{d}{n})$
- $=\sum_{n|x}f(x)\sum_{d'|\frac{x}{n}}\mu(d')$
- $=\sum_{n|x}f(x)\epsilon(\frac{x}{n})$
- $=f(n)$
线性筛$\mu(n)$
inline void MU(int n) {
mu[1]=1; for(R i=2;i<=n;++i) {
if(!vis[i]) pri[++cnt]=i,mu[i]=-1;
for(R j=1;j<=cnt&&pri[j]*i<=n;++j) {
vis[i*pri[j]]=true;
if(i%pri[j]==0) break;
mu[i*pri[j]]=-mu[i];
}
}
}
- 一些进入题目的方法（大佬博客）：
- 形如$\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)==1]$,直接换成$\sum_{i=1}^N\sum_{j=1}^M\sum_{d|gcd(i,j)}\mu(d)$,然后把$d$提出来,写成$\sum_{i=1}^{\frac{N}{d}}\sum_{j=1}^{\frac{M}{d}}\sum_{d=1}^N\mu(d)$，即$\sum_{d=1}^N\mu(d)\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor$
- 形如$\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)==k]$,直接改成$\sum_{i=1}^{\lfloor\frac{N}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{k}\rfloor}[gcd(i,j)==1]$
- 形如$\sum_{i=1}^N\sum_{j=1}^Mij[gcd(i,j)==k]$（见大佬博客）
- 形如$\sum_{i=1}^N\sum_{j=1}^Mlcm(i,j)$(见我的or大佬博客)
- 形如$\sum_{i=1}^N\sum_{j=1}^Mgcd(i,j)$,直接用欧拉反演化成$\sum_{i=1}^{N}\sum_{j=1}^M\sum_{d|gcd(i,j)}\varphi(d)$,然后把$d$提出来$\sum_{i=1}^{\lfloor \frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{M}{d} \rfloor}\sum_{d=1}^N\varphi(d)$,即$\sum_{d=1}^N\varphi(d)\lfloor \frac{N}{d}\rfloor \lfloor \frac{M}{d} \rfloor$
- 所以当有一个类似$\sum_{d|gcd(i,j)}$的式子时，大致要把它拆掉，把$i.j$除以$n$,成为$.../n,\sum_{d=1}^{N}$（显然=。=）
4.整除分块
- 求$\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$时，
- 随便$O(n)$求，可是我们要$O(\sqrt{n})$去求；
- 通过观察，发现$ \lfloor \frac{n}{i} \rfloor $在一定区间内是不变的，并且每个区间的右端点都是$n/ \lfloor n/i \rfloor $，得出这个结论后就可以$O(\sqrt{n})$去求
for(R l=1,r;l<=n;l=r+1) { r=min(n/(n/l),n); ans+=(r-l+1)*(n/l); }
- 有时候，可能推出来的式子不一定就是一个很裸的整除分块，可能会与某些积性函数相乘，如：$\mu,\varphi$...... 这时候，我们就需要对这些函数统计一个前缀和。因为，每当我们使用整除分块跳过一个区间的时候，其所对应的函数值也跳过了一个区间。所以此时，就需要乘上那一个区间的函数值。
5.欧拉函数
- 有一个性质$\sum_{d|n} \varphi(d)=n$
- 所以造就了欧拉反演（雾）（大佬的详解）
- 求$\sum_{i=1}^N\sum_{j=1}^M\space gcd(i,j)\space(n<m)$
- 原式
- $=\sum_{i=1}^N\sum_{j=1}^M\sum_{d|gcd(i,j)}\varphi(d)$
- 把$d$提出来
- $=\sum_{i=1}^{\lfloor \frac{N}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{M}{d} \rfloor} \sum_{d=1}^N\varphi(d)$
- $=\sum_{d=1}^{N}\varphi(d)\lfloor \frac{N}{d} \rfloor\lfloor \frac{M}{d} \rfloor$