莫比乌斯反演 学习笔记

目录

• 定义
• 性质
• 线性筛求莫比乌斯函数
• 莫比乌斯变换

定义

\[\mu(x)= \left\{ \begin{aligned} 1 & & & n=1\\ 0 & & & n\ \text{有平方因子} \\ \left(-1\right)^k & & & k \text{为}\ n\ \text{的本质不同的质因子数} \end{aligned} \right. \]

性质

首先莫比乌斯函数式积性函数，也就是说，\(\forall x,y\in\mathbb{N}_+,\gcd(x,y)=1\)，有 \(\mu(x)\times\mu(y)=\mu(x\times y)\)。
证明显然。

---

当然它还有一个更加有用的性质。

\[\sum_{d|n}\mu(d)= \left\{ \begin{aligned} 1 & & n=1\\ 0 & & n\not=1 \end{aligned} \right. \]

证明：
设

\[n=\prod\limits^{k}_{i=1} p_i^{c_i},n'=\prod\limits^{k}_{i=1}p_i \]

那么

\[\sum\limits_{d|n}\mu(i)=\sum\limits_{d|n}\mu(i)=\sum\limits_{i=0}^{k}C^{i}_{k}\left(-1\right)^{i}=\left(1+\left(-1\right)\right)^k \]

显然只有 \(k=0\)，也就是 \(n=1\) 的时候左边的式子为 \(0\)，否则为 \(1\)。

换句话说，也就是

\[\left[n=1\right]=\varepsilon\left(n\right)=\sum_{d|n}\mu(d) \]

线性筛求莫比乌斯函数

根据定义，不难写出代码：

void init(){
	int i,j; mu[1]=1; cnt=0; isp[1]=1; for(i=2;i<=N;i++){
		if(!isp[i]) pr[++cnt]=i,mu[i]=-1;
		for(j=1;j<=cnt&&i*pr[j]<=N;j++){
			isp[i*pr[j]]=1; mu[i*pr[j]]=-mu[i];
			if(i%pr[j]==0){ mu[i*pr[j]]=0; break; }
		}
	} for(i=2;i<=N;i++) mu[i]+=mu[i-1]; return;
}

莫比乌斯变换

设有两个数论函数 \(f(x),g(x)\)。
如果有 \(f(n)=\sum_{d|n}g(d)\)，那么 \(g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})\)。

另一种形式：
如果 \(f(n)=\sum_{n|d}g(d)\)，那么 \(g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)\)。