前導

要學習莫比烏斯函式 需要學習 到 積性函式，深度理解歐拉篩，

先說說什么是積性函式吧，

積性函式

其實積性函式非常好理解，
定義

積性函式：若gcd(a,b)=1，且滿足f(ab)=f(a)f(b)，則稱f(x)為積性函式
完全積性函式：對于任意正整數a，b，都滿足f(ab)=f(a)f(b)，則稱f(x)為完全積性函式
性質

1.若f(n),g(n)均為積性函式，則函式h(n)=f(n)g(n)也是積性函式
2.若f(n)為積性函式，則函式c*f(n)(c是常數)也是積性函式，反之一樣
3.任何積性函式都能應用線性篩，在O(n)時間內求出1~n項(莫比烏斯就要用到)，像素數，歐拉函式等都是 積性函式，

知道這些之后，我們就來看莫比烏斯函式，

莫比烏斯函式

定義：
莫比烏斯函式主要是個分段函式，

性質：
1.對于任意正整數n， ∑ d ∣ n n μ ( d ) = [ n = 1 ] \sum_{d|n}^{n}{μ(d)=[n=1]} ∑d∣nn?μ(d)=[n=1] ，（[n==1]表示只有當n=1成立時，回傳值為1；否則，值為0；(這個就是用μ是容斥系數的性質可以證明)(PS:這一條性質是莫比烏斯反演中最常用的)

2.對于任意正整數n， ∑ d ∣ n n μ ( d ) d = ? ( n ) n \sum_{d|n}^{n}{\frac{μ(d)}{d}=\frac{?(n)}{n}} ∑d∣nn?dμ(d)?=n?(n)? （這個性質很奇妙，它把歐拉函式和莫比烏斯函式結合起來）

強烈建議 ： 深度理解完這兩條性質之后，在去看莫比烏斯反演，要不莫比烏斯反演不容易懂，

至于如何求莫比烏斯函式：我們知道莫比烏斯函式跟歐拉函式一樣都是積性函式，所以我們可以同 歐拉篩一樣吧莫比烏斯函式篩出來，

void get_mu(ll n){
	mu[1]=1;// 存放 莫比烏斯函式；
	//isprime[] 存放 是否是質數
	//prime[]  存放  質數 
	for(int i=2;i<=n;i++){
		if(!isprime[i]) {
			prime[++cnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
			isprime[i*prime[j]]=1;
			if(i%prime[j]==0){mu[i*prime[j]]=0;break;}//也可以直接break 因為里面本來存的就是0 
			else mu[i*prime[j]]=-mu[i];			
		}		
	} 
}

莫比烏斯反演

我只是掌握皮毛，有深層次的理解在更新，有更好的理解也可以分享給我哦~~~， 不勝感激！

莫比烏斯反演的引入：

若 F ( n ) = ∑ d ∣ n n f ( d ) F(n)=\sum_{d|n}^{n}{f(d)} F(n)=∑d∣nn?f(d).

那么
從中，可以看出，若 n=p²(p是質數)那么 F ( p ) = f ( 1 ) + f ( p ) , F ( n ) = f ( 1 ) + f ( p ) + f ( p 2 ) F\left( p \right)=f\left( 1 \right)+f\left( p \right),F\left( n \right)=f\left( 1 \right)+f\left( p \right)+f\left( p^2 \right) F(p)=f(1)+f(p),F(n)=f(1)+f(p)+f(p2),所以 f ( n ) = F ( p 2 ) ? F ( p ) f\left( n \right)=F\left( p^2 \right)-F\left( p \right) f(n)=F(p2)?F(p)
通過推廣我們可以得到就像n=8，(！=p²) 他也滿足這個式子

f ( n ) = ∑ d ∣ n n u ( d ) F ( n d ) f\left( n \right)=\sum_{d|n}^{n}{u\left( d \right)}{F\left( \frac{n}{d} \right)} f(n)=∑d∣nn?u(d)F(dn?)

根據上個推廣的來的式子我們 就可以說 莫比烏斯反演定理了，

莫比烏斯反演定理

設 f ( n ) f\left ( n \right) f(n) 和 g ( n ) g\left( n \right) g(n)是定義在正整數集合上的兩個函式定義如下:
若函式 f ( n ) f\left( n \right) f(n)函式:
f ( n ) = ∑ d ∣ n n g ( d ) = ∑ d ∣ n g ( n d ) f\left( n \right)=\sum_{d|n}^{n}{g\left( d \right)}=\sum_{d|n}^{}{g\left( \frac{n}{d} \right)} f(n)=∑d∣nn?g(d)=∑d∣n?g(dn?)
則有：

莫比烏斯反演定理證明

參考著個吧
理解就行，重要是定理，(個人認為)

莫比烏斯反演另一性質(與歐拉函式有關)

若n>1且n為正整數，則有 ∑ d ∣ n u ( d ) = 0 \sum_{d|n}^{}{u\left( d \right)}=0 ∑d∣n?u(d)=0
若n=1，則該式為1、
2，
對任意正整數n均有：

∑ d ∣ n u ( d ) d = ? ( n ) n \sum_{d|n}^{}{\frac{u\left( d \right)}{d}}=\frac{\phi \left( n \right)}{n} ∑d∣n?du(d)?=n?(n)?