莫比乌斯反演-从莫比乌斯到欧拉

让我们从一道题开始 求$$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j),(n<m)$$ 首先对$gcd(i,j)$分类，有 $$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)$$ $$=\sum_{k=1}^{n}k\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]$$ 同时除以$k$ $$=\sum_{k=1}^{n}k\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]$$ $$=\sum_{k=1}^{n}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}^{n}k\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)*\lfloor\frac{n}{kd}\rfloor*\lfloor\frac{m}{kd}\rfloor$$ 首先注意到$\lfloor\frac{n}{k}\rfloor$，这个东西是可以分块的 而之后的$\lfloor\frac{n}{kd}\rfloor*\lfloor\frac{m}{kd}\rfloor$也是可以分块的！ 所以总时间复杂度降到了$O(\sqrt n*\sqrt n)=O(n)$！ 但我们还有更优秀的方法 设$T=kd$,枚举$T$，可以得到 $$=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor\sum_{k|T}k*\mu(\frac{T}{k})$$ 我们考虑最后那个式子 $$\sum_{k|T}k*\mu(\frac{T}{k})$$ 可以发现，这是个**狄利克雷卷积**的标准式 $$=(id*\mu)(T)\ \ \ \ id(x)=x$$ 首先有$$(1*\varphi)=id$$ $$\sum_{x|n}\varphi(x)=n=id(n)$$ 所以$$=(1*\varphi*\mu)(T)$$ $$=((1*\mu)*\varphi)(T)$$ 而 $$(1*\mu)(T)=\sum_{x|T}\mu(x)=e\ \ \ \ ([T=1])$$ 因此 $$=(e*\varphi)(T)$$ $$=\varphi(T)$$ $$\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor\sum_{k|T}k*\mu(\frac{T}{k})$$ $$=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor*\varphi(T)$$ 这样，我们就从$O(n)$降到了$O(\sqrt n)$！ --- 这里说一句： ## 其实，上面的做法，都是吃多了的做法 回到题目： 求$$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j),(n<m)$$ 显然，我们有$$\sum_{d|n}\varphi(d)=n$$ 把那个$n$换成$gcd(i,j)$ $$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\varphi(d)$$ 对$d$进行分类 $$=\sum_{d=1}^{n}\varphi(d)*\lfloor\frac{n}{d}\rfloor*\lfloor\frac{m}{d}\rfloor$$ 完了 我就暂且把这种神奇的方法叫作**欧拉反演**吧