莫比乌斯反演-让我们从基础开始

**提示：对于这种与gcd有关的式子别用莫比乌斯反演公式，会炸的** 只需要记住： $$[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)$$ 证明？其实很简单。 $\mu$函数有个性质 $$\sum_{d|n}\mu(d)=[n=1]$$ 将$d$替换成$gcd(i,j)$就是上面的那个暂且可以称作公式的式子了 # 例1 求$$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]\ \ \ \ (n<m)$$ 直接套公式啦 $$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d)$$ 然后我们枚举$d$，显然有$d\in(1,n)\ \ \ (d|gcd(i,j))$ 于是将$d$提到前面去，则$i,j$都是$d$的倍数，化简一下，得 $$=\sum_{d=1}^{n}\mu(d)*\lfloor\frac{n}{d}\rfloor*\lfloor\frac{m}{d}\rfloor$$ 注意到后面那一坨是可以$O(\sqrt n)$分块做的 于是我们实现了$O(n^2)$到$O(\sqrt n)$的过渡 简单吧 # 例2 求 $$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]\ \ \ \ (n<m)$$ 好像与上一题有点不一样 但我们可以转化成一样的 同时除以$k$，得 $$=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]$$ 然后就一样了 # 例3 求 $$\sum_{i=1}^{n}\sum_{j=1}^{m}ij[gcd(i,j)=k]\ \ \ \ (n<m)$$ 老方法，同时除以$k$，只不过与上一题不同的是，我们需要考虑$i,j$的贡献 $$=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij[gcd(i,j)=1]*k^2$$ 有同学可能要问了 > 为什么最后要乘以一个$k^2$啊？ 因为在$i,j$同时除以$k$的同时，中间那个$ij$的值就变了，$i,j$同时缩小到了原来的$\frac{1}{k}$，所以最后要把缩小的乘回来，就是$k^2$ 让我们继续套路，将中间那个$gcd(i,j)$用莫比乌斯替换掉 $$=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij\sum_{d|gcd(i,j)}\mu(d)*k^2$$ 提出$d$，同样，在最后乘以一个$d^2$ $$=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)*d^2\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}ij*k^2$$ 各归各家，各找各妈 $$=k^2*\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)*d^2\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}j$$ 我们发现，最后那两项，不就是$\dots$**等差数列**吗？ 时间复杂度$O(n^2)\rightarrow O(\sqrt n)$ **来一个强的** # 例4 求$$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$$ 首先，小学奥数告诉我们 $$lcm(i,j)=\frac{i*j}{gcd(i,j)}$$ 可以看看我的另外一篇博客[**莫比乌斯反演-从莫比乌斯到欧拉**](https://www.luogu.org/blog/An-Amazing-Blog/ji-miao-di-mu-bi-wu-si-fan-yan)，里面详细地介绍了一种奇妙的反演方法，大致思路是用$\phi$函数替换$\mu$函数。我暂且把它叫做**欧拉反演**。 但是注意，如果$gcd(i,j)$出现在分母这种不正常的位置，就不能用那个神奇的欧拉反演，而应该用常规方法。 先科普一下：[积性函数](https://baike.baidu.com/item/%E7%A7%AF%E6%80%A7%E5%87%BD%E6%95%B0/8354949)，稍后会有用的 仍然是老套路，枚举$gcd(i,j)$ $$=\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}{d}*[gcd(i,j)=d]$$ 同时除以$d$ $$=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i*j*d*[gcd(i,j)=1]$$ $$=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i*j*d\sum_{k|gcd(i,j)}\mu(k)$$ 枚举$k$ $$=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)*k^2\sum_{i=1}^{\lfloor\frac{n}{dk}\rfloor}i\sum_{j=1}^{\lfloor\frac{m}{dk}\rfloor}j$$ 这时，这已经是一个$O(n)$的做法，观察可以得到，$\lfloor\frac{n}{d}\rfloor$可以分一次块，$\lfloor\frac{n}{dk}\rfloor$可以再分一次块，总时间复杂度是$O(\sqrt n*\sqrt n)=O(n)$ 推到这里已经很牛逼了，但我们还有更好的方法，这个时间复杂度还能优化 后面那两坨等差数列很烦，我们把它换掉 设$T=dk,f(x)=\sum_{i=1}^{x}i$，把原来那个式子换成 $$=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)*k^2*f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)$$ **看好了，下面的步骤很奇妙** 用枚举$gcd(i,j)$的方法，我们枚举$T$ $$=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}d*\mu(\frac{T}{d})*(\frac{T}{d})^2$$ $$=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}d*\mu(d)*T$$ em$\dots$貌似没法用狄利克雷卷积 但别担心，我们观察最后这个式子 $$\sum_{d|T}d*\mu(d)*T$$ 先不管$T$ $$\sum_{d|T}d*\mu(d)$$ 设$$F(T)=\sum_{d|T}d*\mu(d)$$ 我们考虑$a\perp b$ $$F(a)=\sum_{d|a}d*\mu(d)$$ $$F(b)=\sum_{d|b}d*\mu(d)$$ 显然$a,b$对$F(ab)$的贡献是没有交集的，而这时，在我们枚举$d$时，它既可以是$a$的约数，也可以是$b$的约数，还能是$ab$的约数。具体来说，$F(a)$的某一项乘$F(b)$的某一项一定等于$F(ab)$的某一项（一个$a$的因子与一个$b$的因子相乘一定是$ab$的因子） 又因为$a\perp b$，故有 $\mu(a$的某个因子$k)*\mu(b$的某个因子$j)=\mu(k*j)$ 所以，$F$不就是一个积性函数吗？ 常识告诉我们，积性函数是可以$O(n)$筛的，$F$也一样 有 $$F(1)=1$$ 如果$a$是质数，则 $$F(a)=1-a$$ 如果$a\perp b$，则 $$F(a*b)=F(a)*F(b)$$ 这三个公式易得出，我们考虑$a\equiv 0\ (mod\ b)$且$b$是质数的情况 则$F(a*b)$比$F(a)$多出的几项中，$d$分解后，项$b$的次数一定大于$1$ 想一想，为什么 因为，如果$b$这一项的次数小于等于$1$，它就一定在$F(a)$中被运算过了！（$a$一定有$b$这个质因子） 别忘了，当某个数的某个质因子次数大于$1$，它的$\mu$值就是$0$啊！ 故此时 $$F(a*b)=F(a)$$ 于是，我们推导出了$F$函数的转移公式，代码表示如下（顺便处理一下前缀和） ``` cpp void sieve() { F[1]=sum[1]=1; for (int i=2;i<=10000000;i++) { if (!flag[i]) prime[++cnt]=i,F[i]=1-i; for (int j=1;j<=cnt&&i*prime[j]<=10000000;j++) { flag[i*prime[j]]=1; if (i%prime[j]==0) {//不互质 F[i*prime[j]]=F[i]; break; } F[i*prime[j]]=F[i]*F[prime[j]];//互质 } sum[i]=sum[i-1]+F[i]*i; } } ``` 回到公式 $$=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}d*\mu(d)*T$$ 仔细看代码，最后那个$T$已经在前缀和中处理了 我们只需要分块求前面那两个$f$，后面那一坨$O(1)$处理（都筛出来了） 时间复杂度$O(n)\rightarrow O(\sqrt n)$ 当你想降一下时间复杂度时，枚举第二个分块中的某一项再进行处理可能是一个好选择。 # 例5 求 $$\sum_{i=1}^{n}\sum_{j=1}^{m}d(i*j)$$ 其中，$d(i*j)$表示$i*j$的约数个数 我们有一个公式 $$d(i*j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$$ 很多人不知道这个公式是怎么推的，我来解释一下 其实，这里的$[gcd(i,j)=1]$并不是为了去重，而是为了和左边的式子保持相等 我们考虑一个质数$p$，$i=i'*p^{k_1},j=j'*p^{k_2}$，注意这里$k_1,k_2$可以为$0$ 考虑$p$对$d(i*j)$的贡献，显然，在$d$的因子中，$p$的这一项可以为$0$~$k_1+k_2$共$k_1+k_2+1$个 考虑等式右边，我们只看$p$这一项。$x=x'*p^{k_x},y=y'*p^{k_y}$ 要满足$gcd(x,y)=1$,那么就有$gcd(p^{k_x},p^{k_y})=1$ 要么$k_x=0,k_y\in[0,k_2]$，共$k_2+1$种 要么$k_y=0,k_x\in[0,k_1]$，共$k_1+1$种 减去重复判断的$k_x=0,k_y=0$这种情况，最后答案$k_1+k_2+1$种 与等式左边相同！ 剩下的步骤都很水了，所以我把这留作练习，如果你认真阅读了以上所有内容，那么这个练习就可以轻松解决。 # 练习 ## 练习1 上面说了 ## 练习2 求 $$\prod_{i=1}^{n}\prod_{j=1}^{m}f[gcd(i,j)]\ \ \ (n,m\leq 10^6,T\leq 1000)$$ $f$是斐波那契数列 ## 练习3 求 $$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k\ \ \ (n,m\leq 5*10^6,T\leq 2000)$$ 注：练习2、练习3中，$T$是数据组数 # 后记 感谢lyc大佬的指导，在他的帮助与耐心解答下，我才初识了~~懵逼钨丝反演~~莫比乌斯反演 只要掌握方法，能够耐心地进行推导，莫比乌斯系列的题目其实不难