专栏文章

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

AAn_Account
个人记录参与者 57已保存评论 82

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
82 条
当前快照
1 份
快照标识符
@mlox5skm
此快照首次捕获于
2026/02/16 16:35
3 周前
此快照最后确认于
2026/03/03 21:21
5 天前
查看原文
提示：对于这种与gcd有关的式子别用莫比乌斯反演公式，会炸的
只需要记住：
[gcd(i,j)=1]=∑d∣gcd(i,j)μ(d)[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)
证明？其实很简单。
μ\mu函数有个性质
∑d∣nμ(d)=[n=1]\sum_{d|n}\mu(d)=[n=1]
将dd替换成gcd(i,j)gcd(i,j)就是上面的那个暂且可以称作公式的式子了

例1

求∑i=1n∑j=1m[gcd(i,j)=1]    (n<m)\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]\ \ \ \ (n<m)
直接套公式啦
=∑i=1n∑j=1m∑d∣gcd(i,j)μ(d)=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d)
然后我们枚举dd，显然有d∈(1,n)   (d∣gcd(i,j))d\in(1,n)\ \ \ (d|gcd(i,j))
于是将dd提到前面去，则i,ji,j都是dd的倍数，化简一下，得
=∑d=1nμ(d)∗⌊nd⌋∗⌊md⌋=\sum_{d=1}^{n}\mu(d)*\lfloor\frac{n}{d}\rfloor*\lfloor\frac{m}{d}\rfloor
注意到后面那一坨是可以O(n)O(\sqrt n)分块做的
于是我们实现了O(n2)O(n^2)到O(n)O(\sqrt n)的过渡
简单吧

例2

求
∑i=1n∑j=1m[gcd(i,j)=k]    (n<m)\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]\ \ \ \ (n<m)
好像与上一题有点不一样
但我们可以转化成一样的
同时除以kk，得
=∑i=1⌊nk⌋∑j=1⌊mk⌋[gcd(i,j)=1]=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]
然后就一样了

例3

求
∑i=1n∑j=1mij[gcd(i,j)=k]    (n<m)\sum_{i=1}^{n}\sum_{j=1}^{m}ij[gcd(i,j)=k]\ \ \ \ (n<m)
老方法，同时除以kk，只不过与上一题不同的是，我们需要考虑i,ji,j的贡献
=∑i=1⌊nk⌋∑j=1⌊mk⌋ij[gcd(i,j)=1]∗k2=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij[gcd(i,j)=1]*k^2
有同学可能要问了
为什么最后要乘以一个k2k^2啊？
因为在i,ji,j同时除以kk的同时，中间那个ijij的值就变了，i,ji,j同时缩小到了原来的1k\frac{1}{k}，所以最后要把缩小的乘回来，就是k2k^2
让我们继续套路，将中间那个gcd(i,j)gcd(i,j)用莫比乌斯替换掉
=∑i=1⌊nk⌋∑j=1⌊mk⌋ij∑d∣gcd(i,j)μ(d)∗k2=\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
提出dd，同样，在最后乘以一个d2d^2
=∑d=1⌊nk⌋μ(d)∗d2∑i=1⌊nkd⌋∑j=1⌊mkd⌋ij∗k2=\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
各归各家，各找各妈
=k2∗∑d=1⌊nk⌋μ(d)∗d2∑i=1⌊nkd⌋i∑j=1⌊mkd⌋j=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(n2)→O(n)O(n^2)\rightarrow O(\sqrt n)
来一个强的

例4

求∑i=1n∑j=1mlcm(i,j)\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)
首先，小学奥数告诉我们
lcm(i,j)=i∗jgcd(i,j)lcm(i,j)=\frac{i*j}{gcd(i,j)}
可以看看我的另外一篇博客莫比乌斯反演-从莫比乌斯到欧拉，里面详细地介绍了一种奇妙的反演方法，大致思路是用ϕ\phi函数替换μ\mu函数。我暂且把它叫做欧拉反演。
但是注意，如果gcd(i,j)gcd(i,j)出现在分母这种不正常的位置，就不能用那个神奇的欧拉反演，而应该用常规方法。
先科普一下：积性函数，稍后会有用的
仍然是老套路，枚举gcd(i,j)gcd(i,j)
=∑d=1n∑i=1n∑j=1mi∗jd∗[gcd(i,j)=d]=\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}{d}*[gcd(i,j)=d]
同时除以dd
=∑d=1n∑i=1⌊nd⌋∑j=1⌊md⌋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*[gcd(i,j)=1]
=∑d=1n∑i=1⌊nd⌋∑j=1⌊md⌋i∗j∗d∑k∣gcd(i,j)μ(k)=\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)
枚举kk
=∑d=1nd∑k=1⌊nd⌋μ(k)∗k2∑i=1⌊ndk⌋i∑j=1⌊mdk⌋j=\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)O(n)的做法，观察可以得到，⌊nd⌋\lfloor\frac{n}{d}\rfloor可以分一次块，⌊ndk⌋\lfloor\frac{n}{dk}\rfloor可以再分一次块，总时间复杂度是O(n∗n)=O(n)O(\sqrt n*\sqrt n)=O(n)
推到这里已经很牛逼了，但我们还有更好的方法，这个时间复杂度还能优化
后面那两坨等差数列很烦，我们把它换掉
设T=dk,f(x)=∑i=1xiT=dk,f(x)=\sum_{i=1}^{x}i，把原来那个式子换成
=∑d=1nd∑k=1⌊nd⌋μ(k)∗k2∗f(⌊nT⌋)∗f(⌊mT⌋)=\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)gcd(i,j)的方法，我们枚举TT
=∑T=1nf(⌊nT⌋)∗f(⌊mT⌋)∑d∣Td∗μ(Td)∗(Td)2=\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
=∑T=1nf(⌊nT⌋)∗f(⌊mT⌋)∑d∣Td∗μ(d)∗T=\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貌似没法用狄利克雷卷积
但别担心，我们观察最后这个式子
∑d∣Td∗μ(d)∗T\sum_{d|T}d*\mu(d)*T
先不管TT
∑d∣Td∗μ(d)\sum_{d|T}d*\mu(d)
设F(T)=∑d∣Td∗μ(d)F(T)=\sum_{d|T}d*\mu(d)
我们考虑a⊥ba\perp b
F(a)=∑d∣ad∗μ(d)F(a)=\sum_{d|a}d*\mu(d)
F(b)=∑d∣bd∗μ(d)F(b)=\sum_{d|b}d*\mu(d)
显然a,ba,b对F(ab)F(ab)的贡献是没有交集的，而这时，在我们枚举dd时，它既可以是aa的约数，也可以是bb的约数，还能是abab的约数。具体来说，F(a)F(a)的某一项乘F(b)F(b)的某一项一定等于F(ab)F(ab)的某一项（一个aa的因子与一个bb的因子相乘一定是abab的因子）
又因为a⊥ba\perp b，故有
μ(a\mu(a的某个因子k)∗μ(bk)*\mu(b的某个因子j)=μ(k∗j)j)=\mu(k*j)
所以，FF不就是一个积性函数吗？
常识告诉我们，积性函数是可以O(n)O(n)筛的，FF也一样
有
F(1)=1F(1)=1
如果aa是质数，则
F(a)=1−aF(a)=1-a 如果a⊥ba\perp b，则
F(a∗b)=F(a)∗F(b)F(a*b)=F(a)*F(b)
这三个公式易得出，我们考虑a≡0 (mod b)a\equiv 0\ (mod\ b)且bb是质数的情况
则F(a∗b)F(a*b)比F(a)F(a)多出的几项中，dd分解后，项bb的次数一定大于11
想一想，为什么
因为，如果bb这一项的次数小于等于11，它就一定在F(a)F(a)中被运算过了！（aa一定有bb这个质因子）
别忘了，当某个数的某个质因子次数大于11，它的μ\mu值就是00啊！
故此时
F(a∗b)=F(a)F(a*b)=F(a)
于是，我们推导出了FF函数的转移公式，代码表示如下（顺便处理一下前缀和）
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;
	}
}
回到公式
=∑T=1nf(⌊nT⌋)∗f(⌊mT⌋)∑d∣Td∗μ(d)∗T=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}d*\mu(d)*T
仔细看代码，最后那个TT已经在前缀和中处理了
我们只需要分块求前面那两个ff，后面那一坨O(1)O(1)处理（都筛出来了）
时间复杂度O(n)→O(n)O(n)\rightarrow O(\sqrt n)
当你想降一下时间复杂度时，枚举第二个分块中的某一项再进行处理可能是一个好选择。

例5

求
∑i=1n∑j=1md(i∗j)\sum_{i=1}^{n}\sum_{j=1}^{m}d(i*j)
其中，d(i∗j)d(i*j)表示i∗ji*j的约数个数
我们有一个公式
d(i∗j)=∑x∣i∑y∣j[gcd(x,y)=1]d(i*j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]
很多人不知道这个公式是怎么推的，我来解释一下
其实，这里的[gcd(i,j)=1][gcd(i,j)=1]并不是为了去重，而是为了和左边的式子保持相等
我们考虑一个质数pp，i=i′∗pk1,j=j′∗pk2i=i'*p^{k_1},j=j'*p^{k_2}，注意这里k1,k2k_1,k_2可以为00
考虑pp对d(i∗j)d(i*j)的贡献，显然，在dd的因子中，pp的这一项可以为00~k1+k2k_1+k_2共k1+k2+1k_1+k_2+1个
考虑等式右边，我们只看pp这一项。x=x′∗pkx,y=y′∗pkyx=x'*p^{k_x},y=y'*p^{k_y}
要满足gcd(x,y)=1gcd(x,y)=1,那么就有gcd(pkx,pky)=1gcd(p^{k_x},p^{k_y})=1
要么kx=0,ky∈[0,k2]k_x=0,k_y\in[0,k_2]，共k2+1k_2+1种
要么ky=0,kx∈[0,k1]k_y=0,k_x\in[0,k_1]，共k1+1k_1+1种
减去重复判断的kx=0,ky=0k_x=0,k_y=0这种情况，最后答案k1+k2+1k_1+k_2+1种
与等式左边相同！
剩下的步骤都很水了，所以我把这留作练习，如果你认真阅读了以上所有内容，那么这个练习就可以轻松解决。

练习

练习1

上面说了

练习2

求
∏i=1n∏j=1mf[gcd(i,j)]   (n,m≤106,T≤1000)\prod_{i=1}^{n}\prod_{j=1}^{m}f[gcd(i,j)]\ \ \ (n,m\leq 10^6,T\leq 1000)
ff是斐波那契数列

练习3

求
∑i=1n∑j=1mgcd(i,j)k   (n,m≤5∗106,T≤2000)\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k\ \ \ (n,m\leq 5*10^6,T\leq 2000)
注：练习2、练习3中，TT是数据组数

后记

感谢lyc大佬的指导，在他的帮助与耐心解答下，我才初识了懵逼钨丝反演莫比乌斯反演
只要掌握方法，能够耐心地进行推导，莫比乌斯系列的题目其实不难

评论

共 82 条评论，欢迎与作者交流。

正在加载评论...