莫比乌斯反演-随手录

随手录1

​ 请注意每个例子的第一行即为问题要求。

​ 如果您觉得我的推导存在问题，那么请评论或私信我。

​ 可能会附上题目位置。

例一 洛谷-P2257 YY的GCD

$\sum_{i=1}^{n}\sum_{j=1}^{m}[~\gcd(i,j)=p~]\tag{p$~$$\in$$~$$\text{prime}$}\\ \sum_{p}^{\max(n,m)}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d|\gcd(i,j)}\mu(d) \\ \sum_{p}^{\max(n,m)}\sum_{d=1}^{\min(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)} \mu(d)\lfloor\frac{n}{d\cdot p}\rfloor\lfloor\frac{m}{d\cdot p}\rfloor \\ k=d \cdot p \\ \sum_{k}^{\min(n,m)} \sum_{p|k}\mu(\frac{k}{p})\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor \\ \sum_{k}^{\min(n,m)}\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor \sum_{p|k}\mu(\frac{k}{p})$

例二

$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j) \\ \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|\gcd(i,j)}\phi(d) \\ \sum_{d=1}^{\min(n,m)}\phi(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$

例三

$\sum_{i=1}^{n}\sum_{j=1}^{m} \frac{1}{\gcd(i,j)} \\ \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{\max(n,m)}\frac{1}{k}[~\gcd(i,j)=k~] \\ \sum_{k=1}^{\max(n,m)}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\frac{1}{k}[~\gcd(i,j)=1~] \\ \sum_{k=1}^{\max(n,m)}\frac{1}{k}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|\gcd(i,j)} \mu(d)\\ \sum_{k=1}^{\max(n,m)}\frac{1}{k}\sum_{d=1}^{\min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\lfloor\frac{n}{d\cdot k}\rfloor\lfloor\frac{m}{d\cdot k}\rfloor \\ l=d\cdot k \\ \sum_{l=1}^{\min(n,m)}\lfloor\frac{n}{l}\rfloor\lfloor\frac{m}{l}\rfloor\sum_{k|l}\frac{1}{k}\cdot\mu(\frac{l}{k})$

例四 洛谷-P1390 公约数的和

$\sum_{i=1}^{n}\sum_{j=i+1}^{n}\gcd(i,j) \\ \frac{1}{2}\Big(\sum_{i=1}^{n}\sum_{j=1}^{n}\gcd(i,j)-\sum_{i=1}^{n}\gcd(i,i)\Big) \\ \frac{1}{2}\Big(\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}k[~\gcd(i,j)=k~]-\sum_{i=1}^{n}i\Big) \\ \frac{1}{2}\Big(\sum_{k=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}k[~\gcd(i,j)=1~]-\frac{(n+1)\cdot n}{2}\Big) \\ \frac{1}{2}\Big(\sum_{k=1}^{n}k\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{d|\gcd(i,j)}\mu(d)\Big)-\frac{(n+1)\cdot n}{4} \\ \frac{1}{2}\Big(\sum_{k=1}^{n}k\sum_{d=1}^{n}\mu(d)\lfloor\frac{n}{d\cdot k}\rfloor\lfloor\frac{n}{d\cdot k}\rfloor\Big)-\frac{(n+1)\cdot n}{4} \\ l=d\cdot k \\ \frac{1}{2}\Big(\sum_{l=1}^{n}\lfloor\frac{n}{l}\rfloor\lfloor\frac{n}{l}\rfloor\sum_{k|l}k\cdot\mu(\frac{l}{k})\Big)-\frac{(n+1)\cdot n}{4}$

​ 例四其实就是例二，$\phi(x)=\sum_{d|n}d\cdot\mu(\frac{n}{d})$，这个可以莫比乌斯变换证明。