給出莫比烏斯函數的定義：

這里的n即u(i)中的i，即i=1時，u(1)=1；i大于1且i中某個質因子的冪超過1，則u(i)=0；否則，u(i)取決于其質因子個數的奇偶性。

這里給出兩個莫比烏斯函數的性質：

簡略證明性質1：
由唯一分解定理，在n的因子中，某個因子的質因子的冪超過1，那么u(d)=0,對于性質1我們不用管他，所以只研究質因子的冪全是1次的因子就行。假設n有質因子k個，那么，性質1可以轉化成以下式子，即在k個質因子中選i個組成因子，因為i是奇數的時候，這個因子的莫比烏斯函數值是-1，所以奇數項全是負的，偶數項全是正的。

由二項式系數奇數項的和等于偶數項的和，在k>0時，這個式子不論k的奇偶，結果就是0；k=0時，即n=1時，這個式子的結果是1。

簡略證明性質2：
先略過，會了再補充。

基于埃氏篩O(nloglogn)的方法求n以內的數的莫比烏斯函數：

const int N=1e6+10; int mo[N]; void init(int n) {mo[1]=1;for(int i=1;i<=n/2;i++){if(mo[i]!=0){for(int j=i*2;j<=n;j+=i)mo[j]-=mo[i];}} }

基于歐拉篩O(n)的方法求n以內的數的莫比烏斯函數：

const int N=1e6+10; bool vis[N]; int p[N],mo[N],cnt=0; void init(int n) {mo[1]=1;for(int i=2;i<=n;i++){if(!vis[i]){p[++cnt]=i;mo[i]=-1;}for(int j=1;j<=cnt;j++){if(i*p[j]>n)break;vis[i*p[j]]=1;if(i%p[j]==0)break;mo[i*p[j]]=-mo[i];}} }

總結

以上是生活随笔為你收集整理的莫比乌斯函数的两种求法（基于欧拉筛、埃氏筛）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。