让我们从一道题开始
求\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j),(n
首先对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*\phi)=id
\sum_{x|n}\phi(x)=n=kd(n)
所以=(1*\phi*\mu)(T)
=((1*\mu)*\phi)(T)
而
(1*\mu)(T)=\sum_{x|T}\mu(x)=e\ \ \ \ ([T=1])
因此
=(e*\phi)(T)
=\phi(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*\phi(T)
这样，我们就从O(n)降到了O(\sqrt n)！
这里说一句：
其实，上面的做法，都是吃多了的做法
回到题目：
求\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j),(n
显然，我们有\sum_{d|n}\phi(d)=n
把那个n换成gcd(i,j)
=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\phi(d)
对d进行分类
=\sum_{d=1}^{n}\phi(d)*\lfloor\frac{n}{d}\rfloor*\lfloor\frac{m}{d}\rfloor
完了
我就暂且把这种神奇的方法叫作欧拉反演吧
网友评论