提示：对于这种与gcd有关的式子别用莫比乌斯反演公式，会炸的

只需要记住：

[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)

证明？其实很简单。

$$\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)}

可以看看我的另外一篇博客莫比乌斯反演-从莫比乌斯到欧拉，里面详细地介绍了一种奇妙的反演方法，大致思路是用\phi函数替换\mu函数。我暂且把它叫做欧拉反演。

但是注意，如果gcd(i,j)出现在分母这种不正常的位置，就不能用那个神奇的欧拉反演，而应该用常规方法。

先科普一下：积性函数，稍后会有用的

仍然是老套路，枚举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函数的转移公式，代码表示如下（顺便处理一下前缀和）

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) ## 练习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大佬的指导，在他的帮助与耐心解答下，我才初识了~~懵逼钨丝反演~~莫比乌斯反演 只要掌握方法，能够耐心地进行推导，莫比乌斯系列的题目其实不难