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

2018-07-13 21:51:44


让我们从一道题开始

求$$\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$$

完了

我就暂且把这种神奇的方法叫作欧拉反演