莫比乌斯函数 学习笔记

基础印象

(μ) 啊这，这就是莫比乌斯函数(Mobiüs function)。

它是积性函数。

(mu(n)=left{egin{array}{ll} 1 & n=1 \ 0 & n ext { 含有平方因子 } \ (-1)^{k} & k ext { 为 } n ext { 的本质不同质因子个数 } end{array} ight.)

比如(30=2*3*5)则(μ(30)=(-1)^3=-1) ，而(12=2^2*3)则(μ(12)=0)

求欧拉函数

求1~n的μ可以线性筛：

void do_miu(){
	miu[1]=1;
	for(int i=2;i<=n;i++){
		if(!u[i])cnt++,pri[cnt]=i,miu[i]=-1;//质数只有一个质因子，miu=-1
		for(int j=1;j<=cnt;j++){
			if(pri[j]*i>n)break;
			u[ pri[j]*i ]=1;
			if(i%pri[j]==0){miu[i*pri[j]]=0;break;}//表示筛过了，所以会有两个相同因数，所以miu为0
	        miu[i*pri[j]]=-miu[i];//多了一个本质不同质因子，乘上负一
		}
	}
}

烦人推导

有一个性质：

• (sum_{d mid n} mu(d)=left{egin{array}{ll} 1 & n=1 \ 0 & n eq 1 end{array} ight.)

乱搞一下：（ 把n换成gcd(i,j) ）

• (sum_{d mid gcd(i,j)} mu(d)=left{egin{array}{ll} 1 & gcd(i,j)=1 \ 0 & gcd(i,j) eq 1 end{array} ight.)

即 ([g c d(i, j)=1]=sum_{d mid g c d(i, j)} mu(d))

例题

应用：ZAP-Queries 求(sum_{i=1}^nsum_{i=1}^m[gcd(i,j)=d])

这相当于

(sum_{i=1}^{n/d}sum_{i=1}^{n/d}[gcd(i,j)=1])

因为这样对于每一组合法i，j，乘上d就是原来的(gcd(i,j)=d)了

由上面的性质得又相当于

(sum_{i=1}^{n/d}sum_{i=1}^{m/d}sum_{c mid gcd(i, j)} mu(c))

这个可以化为

(sum_{c=1}^nsum_{i=1}^{n/cd}sum_{i=1}^{m/cd}mu(c))

因为这样使得对于任意一组(i,j)都有(ic,jc) ，可以(cmidgcd(i,j)) 然后乘上(mu(c))

我们发现μ已经和i，j没有关系了，就相当于乘上了((n/cd)*(m/cd)个μ(c))

(sum_{c=1}^nμ(c)*(n/cd)*(m/cd))

最终的式子就是如此了。整除分块使得Time: (O(n)→O(sqrt{n}))。

应用：Sky Code

待填坑

莫比乌斯反演的公式：

• 如果有 (F(n)=sum_{d mid n} G(d))

那么会有下面两个结论：

• (G(n)=sum_{d mid n} mu(d) Fleft(leftlfloorfrac{n}{d} ight floor ight))

• (G(n)=sum_{n mid d} muleft(frac{d}{n} ight) F(d))