今天死磕莫比乌斯反演

零基础的移步到这里

复习

莫比乌斯函数
\mu(n)=\left\{\begin{matrix}1&n=1\\0&n含有平方因子\\(-1)^k&k为n的本质不同质因子个数\end{matrix}\right.
一个重要的小性质
\sum\limits_{d|n}\mu(d)=\left\{\begin{matrix}1&n=1\\0&n\ne1\end{matrix}\right.
一个重要的小推论
\left[\gcd(i,j)=1\right]=\sum\limits_{d|\gcd(i,j)}\mu(d)

应用

先来一个小问题入手
求
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\left[\gcd(i,j)=k\right]
设法把原式化为“小推论”的形式
\sum\limits_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\left[\gcd(i,j)=1\right]
套用推论
\sum\limits_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum\limits_{d|\gcd(i,j)}\mu(d)
条件d|\gcd(i,j)等价于d|i,d|j，所以
\sum\limits_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum\limits_{d|i,d|j}\mu(d)
改变求和顺序，先枚举i,j的最大公约数d，再枚举i,j。i,j应为d的倍数
\sum\limits_{d=1}\mu(d)\sum\limits_{i=1,d|i}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j=1,d|j}^{\left\lfloor\frac{m}{k}\right\rfloor}
由于1\sim \left\lfloor\frac{n}{k}\right\rfloor中，d的倍数有\left\lfloor\frac{n}{kd}\right\rfloor个，所以原式化为
\sum\limits_{d=1}^{\min(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor)}\mu(d)\left\lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor
式子左半部分可以用欧拉筛预处理，右半部分数论分块解决
把这题稍微改一下
求
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)
这下\left[\gcd(i,j)=k\right]的形式没了，怎么处理呢？

遇到困难要找警察叔叔，没有困难要制造困难找警察叔叔
——某数学教练

转化一下
\sum\limits_{k=1}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\left[\gcd(i,j)=k\right]
提出k
\sum\limits_{k=1}k\sum\limits_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\left[\gcd(i,j)=1\right]
按前面的方法处理一下
\sum\limits_{k=1}k\sum\limits_{d=1}\mu(d)\left\lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor
令T=dk，得
\sum\limits_{T=1}\sum\limits_{k|T}k\mu(\frac{T}{k})\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor
然后要用到一个神奇的小结论：恒等函数与莫比乌斯函数的狄利克雷卷积为欧拉函数
即
\sum\limits_{d|n}d\mu(\frac{n}{d})=\varphi(n)
所以原式化为
\sum\limits_{T=1}^{\min(n,m)}\varphi(T)\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor
同样欧拉筛加数论分块