莫比乌斯反演
2026-07-30
前置知识
莫比乌斯函数
莫比乌斯函数定义为:
μ(n)=⎩⎨⎧1,0,(−1)k,n=1,n 中含有平方因子,n 能分解为 k 个互异素数相乘.
根据定义式,我们可以得到一个极其重要的性质:
d∣n∑μ(d)=[n=1]
证明
令 n=∏i=1kpiei,n′=∏i=1kpi,根据二项式定理,有
d∣n∑μ(d)=d∣n′∑μ(d)=i=0∑k(ik)(−1)i=(1+(−1))k=[k=0]=[n=1]
莫比乌斯反演
设 f(n),g(n) 是两个数论函数,则有
f(n)=d∣n∑g(d)⟺g(n)=d∣n∑μ(dn)f(d)
由于 Dirichlet 卷积并不要求先后顺序,我们还有另一种写法:
g(n)=n∣d∑f(d)⟺f(n)=n∣d∑μ(nd)g(d)
证明(摘自 OI Wiki)
直接验证,有:
d∣n∑μ(dn)f(d)=d∣n∑μ(dn)k∣d∑g(k)=k∣n∑g(k)d∣n∑[k∣d∣n]μ(dn)=k∣n∑g(k)d∣n∑[dn∣kn]μ(dn)=k∣n∑g(k)[kn=1]=g(n)
式子变形的关键在于交换求和次序,并注意到 k∣d∣n 就等价于 dn∣kn。倒数第二个等号相当于对 kn 的因子 dn 处的莫比乌斯函数求和,所以就等于 [kn=1]。这一表达式仅在 n=k 处不是 0,最后就会得到 g(n)。
