• 本文为博主原创，未经许可不得转载

引入

莫比乌斯反演是数论中的重要内容，在许多情况下能够简化运算。

我们来看这个函数$F(n)=\sum_{d|n}^{ } f(d)$，则有：

$F(1)=f(1)$
$F(2)=f(1)+f(2)$
$F(3)=f(1)+f(3)$
$F(4)=f(1)+f(2)+f(4)$
$F(5)=f(1)+f(5)$
$F(6)=f(1)+f(2)+f(3)+f(6)$
$F(7)=f(1)+f(7)$
$F(8)=f(1)+f(2)+f(4)+f(8)$

于是我们可以通过$F(n)$推导出$f(n)$

$f(1)=F(1)$
$f(2)=F(2)-F(1)$
$f(3)=F(3)-F(1)$
$f(4)=F(4)-F(2)$
$f(5)=F(5)-F(1)$
$f(6)=F(6)-F(3)-F(2)+F(1)$
$f(7)=F(7)-F(1)$
$f(8)=F(8)-F(4)$

观察以上式子的系数，我们做出如下猜想：$f(n)=\sum_{d|n}^{ }\mu (d)F(\frac{n}{d})$

那么这个猜想到底是否正确呢？上式中的$\mu (d)$又是什么呢？

诸位，让我们进入正题，翱翔在数学的天空中吧。

莫比乌斯函数

定义

记莫比乌斯函数为$\mu (d)$，d为正整数

若$d=1$，则$\mu (d)=1$

若$d={p_{1}}{p_{2}} {p_{3}}…{p_{k}}$，则$\mu (d)=(-1)^k$

其他情况下$\mu (d)=0$

性质一

对于任意正整数n

若$n=1$，则$\sum_{d|n}^{ } \mu (d)=1$

若$n>1$，则$\sum_{d|n}^{ } \mu (d)=0$

证明：

（1）当$n=1$时，显然成立
（2）当$n\neq 1$时，将n分解为$n={p_{1}}^{a_{1}}{p_{2}}^{a_{2}}…{p_{k}}^{a_{k}}$
在n的所有因子中，值不为零的只有所有质因子次数都为1的因子，其中质因数个数为r个的因子有$C_{k}^{r}$个
那么显然有：$\sum_{n|d}^{ }\mu(d)=C_{k}^{0}-C_{k}^{1}+C_{k}^{2}+…+(-1)^{k}C_{k}^{k}=\sum_{i=0}^{k}(-1)^{i}C_{k}^{i}$
根据二项式定理：$(x+y)^{n}=\sum_{i=0}^{n}C_{n}^{i}x^{i}y^{n-i}$
令$x=1，y=-1$，代入即可得证

性质二

• 温馨提示：此性质涉及欧拉函数和莫比乌斯定理，读者可先学习之

对于任意正整数n有：$\sum_{d|n}^{ }\frac{\mu(d)}{d}=\frac{\phi (n)}{n}$

证明：
因为$n=\sum_{d|n}^{ }\phi(d)$
所以令$F(n)=n,f(n)=\phi(n)$
代入莫比乌斯定理得：$\phi(n)=\sum_{d|n}^{ }\mu(d)F(\frac{n}{d})$
即$\sum_{d|n}^{ }\frac{\mu(d)}{d}=\frac{\phi (n)}{n}$

积性函数

数论上积性函数的定义：设$f(n)$为定义在$\mathbb{N^{+}}$上的函数，若对于任意的$\gcd (x,y)=1$，都有$f(xy)=f(x)f(y)$，则称$f(x)$为积性函数

积性函数的性质：

（1）$f(1)=1$

（2）积性函数的前缀和也是积性函数

莫比乌斯函数就是一个积性函数(我不会证明)

所以我们可以通过线性筛来求莫比乌斯函数

参考代码

1
2
3
4
5
6
7
8
9
10
11
12

int cnt,check[MAXN],prime[MAXN],mu[MAXN];
void pre(){
	mu[1]=1;
	for(int i=2;i<=MAXN;++i){
		if(!check[i])  prime[++cnt]=i,mu[i]=-1; 
		for(int j=1;j<=cnt&&prime[j]*i<=MAXN;++j){
			check[prime[j]*i]=1;
			if(i%prime[j]==0) {mu[prime[j]*i]=0;break;} 
			mu[prime[j]*i]=-mu[i]; 
		}
	}
}

例题

• 【bzoj2440】完全平方数 【传送门】 【题解传送门】

莫比乌斯定理

因数形式

$F(n)=\sum_{d|n}^{ }f(d)\Leftrightarrow f(n)=\sum_{d|n}^{ }\mu(d)F(\frac{n}{d})$

证明：
$\sum_{d|n}^{ }\mu(d)F(\frac{n}{d})=\sum_{d|n}^{ }\mu(d)\sum_{k|\frac{n}{d}}^{ }f(k)=\sum_{k|n}^{ }f(k)\sum_{d|\frac{n}{k}}^{ }\mu(d)$
根据性质一，当且仅当$\frac{n}{k}=1$时，$\sum_{d|\frac{n}{k}}^{ }\mu(d)$不为0
所以原式=$f(n)$，证毕

倍数形式

$F(n)=\sum_{n|d}^{ }f(d)\Leftrightarrow f(n)=\sum_{n|d}^{ }\mu(\frac{d}{n})F(d)$

证明：
令$k=\frac{d}{n}$，则$\sum_{n|d}^{ }\mu(\frac{d}{n})F(d)=\sum_{k=1}^{+\infty}\mu(k)F(nk)=\sum_{k=1}^{+\infty}\mu(k)\sum_{nk|d}^{ }f(d)=\sum_{n|d}^{ }f(d)\sum_{k|\frac{d}{n}}^{ }\mu(k)$
根据性质一，当且仅当$\frac{d}{n}=1$时，$\sum_{k|\frac{d}{n}}^{ }\mu(k)$不为0
所以原式=$f(n)$，证毕

应用

对于一些函数f(n)，如果我们很难直接求出它的值，而容易求出倍数和或约数和F(n)，那么我们可以通过莫比乌斯反演来求得f(n)的值

例：f(n)表示某一范围内(x,y)=n的数对的数量，F(n)表示某一范围内n|(x,y)的数对的数量

那么直接求f(n)并不是很好求，而F(n)求起来相对无脑一些，我们可以通过对F(n)进行莫比乌斯反演来求得f(n)

例题

• 【bzoj2301】【传送门】 【题解传送门】
• 【bzoj2820】【传送门】 【题解传送门】

参考文献

• 《莫比乌斯反演》——PoPoQQQ 传送门
• 《莫比乌斯反演定理证明（两种形式）》——outer_form 传送门