莫比烏斯函數(shù)

對于$n\ge 0$，設數(shù)$n$的唯一分解式為$P_1^{{\rho }_1}{P}_2^{{\rho }_2}...P_n^{{\rho }_n}$

$\mu (n)=?\begin{array}{rcl}1& & n=1\\ (?1{)}^s& & {\rho }_1={\rho }_2=...={\rho }_s=1\\ 0& & ?{\rho }_i\ge 2\end{array}$

通俗地講，莫比烏斯函數(shù)就是：

$\mu (1)=1$

若$n$存在平方因子，$\mu (n)=0$

若$n$是奇數(shù)個不同素數(shù)之積，$\mu (n)=?1$

若$n$是偶數(shù)個不同素數(shù)之積，$\mu (n)=1$

性質(zhì)

• 性質(zhì)一：莫比烏斯函數(shù)是積性函數(shù)。若$gcd(n,m)=1$，則$\mu (nm)=\mu (n)\mu (m)$

  證明：對$n,m$唯一分解然后分類討論即可

• 性質(zhì)二：設$n\ge 1$，$d|n$（$d$是$n$的因子）

  ${\sum }_{d|n}\mu (d)=[\frac{1}{n}]=\{\begin{array}{rcl}1& & n=1\\ 0& & n\ge 2\end{array}$

  證明：$n=1$時顯然滿足；設$n\ge 2$，數(shù)$n$的唯一分解式為$P_1^{{\rho }_1}{P}_2^{{\rho }_2}...P_s^{{\rho }_s}$，$d$的唯一分解式為$P_1^{{\alpha }_1}{P}_2^{{\alpha }_2}...P_s^{{\alpha }_s}$。根據(jù)莫比烏斯函數(shù)的定義和積性函數(shù)的性質(zhì)可以得出：

  $$\begin{gathered} {\sum }_{d|n}\mu (d)={\sum }_{{\alpha }_1=1}^0{\sum }_{{\alpha }_2=1}^0...{\sum }_{{\alpha }_s=1}^0\mu (P_1^{{\alpha }_1}{P}_2^{{\alpha }_2}...P_s^{{\alpha }_s}) \\ ={\sum }_1^0\mu (P_1^{{\alpha }_1}){\sum }_1^0\mu (P_2^{{\alpha }_2})...{\sum }_1^0\mu (P_s^{{\alpha }_s}) \end{gathered}$$

  對于某一項${\sum }_1^0\mu (P_t^{{\alpha }_t})=1+(?1)=0$，那么所有項乘起來仍為$0$，原式得證。

• 性質(zhì)三：${\sum }_{d|n}\frac{\mu (d)}{d}=\frac{\phi (n)}{n}$

  證明參見莫比烏斯反演關于$\phi (n)={\sum }_{d|n}\mu (d)\frac{n}{d}$的證明

求莫比烏斯函數(shù)

求單個數(shù)

int getMu(int n) {if (n == 1) return 1;int m = sqrt(n + 0.5), cnt = 0;for (int i = 2; i <= m; i++) {if (n % i == 0) {if (n % (i * i) == 0) return 0;n /= i;cnt++;}}if (n > 1) cnt++;return cnt & 1 ? -1 : 1; }

線性篩選

若$i\%prime[j]!=0$，代表$i$中不含該質(zhì)因子，也就是說乘上該質(zhì)因子后恰好會多出一個系數(shù)為$1$質(zhì)因子，因此$\mu (i?prime[j])=?\mu (i)$；

否則代表含有該質(zhì)因子且系數(shù)會大于等于$2$，那么$\mu (i?prime[j])=0$

bool isprime[maxn]; int mu[maxn], prime[maxn];void initMu() {mu[1] = 1;int cnt = 0;for (int i = 2; i < maxn; i++) {if (!isprime[i]) prime[cnt++] = i, mu[i] = -1;for (int j = 0; j < cnt && i * prime[j] < maxn; j++) {isprime[i * prime[j]] = 1;if (i % prime[j]) mu[i * prime[j]] = -mu[i];else {mu[i * prime[j]] = 0;break;}}} }

總結

以上是生活随笔為你收集整理的莫比乌斯函数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。