莫比乌斯反演

莫比乌斯函数

定义

(d)进行质因数分解:(d=p_1^{r1}p_2^{r2}p_3^{r3}····p_k^{rk})
(r=max{r_1,r_2,r_3···r_k})
莫比乌斯函数的定义为

[mu(d) = egin{cases}1qquad d=1\ 0qquad r > 1\ (-1)^kqquad r=1end{cases} ]

也就是说

  • (d=1)时,(mu(d)=1)
  • (d)质因数分解后,若质因子中的最大次数大于一,(mu(d)=0)
  • (d)质因数分解后,质因子中的最大次数等于一,也就是(d=p_1p_2p_3···p_k)时,(mu(d)=(-1)^k)(k)为质因子的个数

举个栗子:
(mu(1)=1\ mu(3)=(-1)^1=-1\ mu(6)=(-1)^2=1\mu(4)=0)

性质

性质1
对于任意正整数(n),有$$sum_{dmid n}mu(d)=[n=1]$$([n=1])表示当(n=1)的时候值为(1),否则值为(0)


证明(请教于wby大佬):
(n=1)时,显然。
考虑(n>1)的情况,(n=p_1^{k1}o_2^{k2}p_3^{k3}···p_m^{km})
根据定义显然只有当(k_1=k_2=k_3=···k_m=1)时有贡献,否则为(0)
我们就只讨论有贡献的情况;
(n)的因子(d)中有(i)个质因子,(mu(d)=(-1)^r),因为(d)的质因子一定是(n)的质因子,从(m)个质因子中选出(i)的质因子的组合数就为(C_m^r)

[sum_{dmid n}mu(d)=sum_{r=0}^{m}(-1)^{i} C_m^r ]

然后根据二项式定理:

[(x+y)^m = sum_{r=0}^{m}C_{m}^{r} x^{m-r} y^r ]

(x=1,y=-1),可得:

[sum_{r=0}^{m}C_m^r(-1)^{r}=sum_{r=0}^{m}C_m^r (1)^{m-r}(-1)^r=(-1+1)^m=0 ]

由此得证


性质2
对于任意正整数(n)均有

[sum_{dmid n} frac{mu(d)}{d}=frac{phi(n)}{n} ]


证明:

[phi(n)=sum_{i=1}^{n}[gcd(i,n)==1] ]

这时根据性质1

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

然后先枚举最大公约数

[egin{aligned} phi(n)=&sum_{dmid n}sum_{dmid i=d}^{ileq n}mu(d)\ =&sum_{dmid n}mu(d)sum_{dmid i=d}^{ileq n}1\ =&sum_{dmid n}mu(d)frac{n}{d}\ =&sum_{dmid n}frac{mu(d)n}{d}end{aligned} ]

得到

[frac{phi(n)}{n}=sum_{dmid n} frac{mu(d)}{d} ]


板子

只需要在筛法上加四句话

void shai(int n) {
	mu[1] = 1;			//定义mu[1]=1 
	for(int i = 2; i <= n; i++) {
		if (!vis[i]) p[++num] = i, mu[i] = -1;	//mu质数=-1 
		for (int j = 1; j <= num; j++) {
			if (i * p[j] > n) break;
			vis[i * p[j]] = 1;
			if (!i % p[j]) {		//i%p[j]==0说明i有p[j]这个因子,所以i*p[j]=0 
				mu[i * p[j]] = 0;
				break;
			} else mu[i * p[j]] = -mu[i];	//有多了一个质因子,所以取负 
		}
	}
}

莫比乌斯反演

略微说明了一下莫比乌斯函数函数后,就迎来最重要的内容,莫比乌斯反演
定义:
如果F(n)f(n)是数论函数,且满足

[F(n)=sum_{dmid n}f(d) ]

则有反演:

[f(n)=sum_{dmid n}mu(d)F(frac{n}{d}) ]


证明:
(F(dfrac{n}{d}))带入得

[sum_{dmid n}mu(d)F(frac{n}{d})=sum_{dmid n}(mu(d)sum_{kmid frac{n}{d}}f(k)) ]

观察后面的式子,发现要满足(dfrac{n}{d}div k=0),所以实际上就是要求

[k imes d=n ]

那我们就可以理解为对于所有的二元组((mu(d),f(k)))都能被枚举到
所以我们枚举(k), 式子就变成了

[sum_{kmid n}(f(k)sum_{k*dmid n}mu(d)) ]

再转换一下,变成

[sum_{kmid n}(f(k)sum_{dmid frac{n}{k}}mu(d)) ]

然后根据莫比乌斯函数的性质1
只有当(k=n)时,(sum_{dmid frac{n}{k}}mu(d)=1),其余情况为(0)
于是原式=(f(n))


莫比乌斯反演的另一种形式:
当$$F(n)=sum_{nmid d}f(d)$$时

[f(n)=sum_{nmid d}f(d)mu(frac{d}{n}) ]

原文地址:https://www.cnblogs.com/lykkk/p/10663073.html