莫比烏斯反演0

棄坑

莫比烏斯函數

定義

設函數$\mu(n)$為莫比烏斯函數

$$\mu =\begin{cases}\left( -1\right) ^{k}\left( n=p_{1}p_{2}\ldots p_{k}\right) \\ O\left( \exists P^{2}|n\right) \\ 1\left( n=1\right) \end{cases}$$

性質

• $\mu(n)$為積性函數
• $$\sum _{d|n}\mu \left( d\right) =\left[ n=1\right]$$(非常重要！！)

莫比烏斯反演

公式

如果

$g\left( n\right) =\sum _{d|n }f\left( d\right)$

那麼

$f\left( n\right) =\sum _{d|n}\mu \left( d\right) g\left( \dfrac {n}{d}\right)$

證明

$$\sum _{d|n}\mu \left( d\right) g\left( \dfrac {n}{d}\right)$$

$$=\sum _{d|n}\mu \left( \dfrac {n}{d}\right) g\left( d\right)$$

$$=\sum _{d|n}\mu \left( \dfrac {n}{d}\right) \sum _{k|d}f\left( k\right)$$

$$=\sum _{k|n}\sum_{d|{\dfrac{n}{k}}}\mu(d)f(k) $$

$$=\sum _{k|n}[\dfrac{n}{k}=1]f(k) $$

$$=f(n)$$

莫比烏斯函數的計算方法

因為$\mu(n)$為積性函數

那麼可以利用線性篩來計算

#include<cstdio>
#include<cstring>
const int MAXN=1e6+10;
int prime[MAXN],mu[MAXN],vis[MAXN],tot,n;
void Euler()
{
    vis[1]=1;mu[1]=1; 
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])    prime[++tot]=i,mu[i]=-1;//隻有一個質因子 
        for(int j=1;i*prime[j]<=n&&j<=tot;j++)
        {
            vis[ i*prime[j] ]=1;
            if(i%prime[j]==0)//i中包含prime[j] 
            {
                mu[ i*prime[j] ]=0;//乘起來之後肯定包含prime[j]^2 
                break; 
            }
            else mu[ i*prime[j] ]=-mu[i];//多了一個質因子 
        }
    }
}
int main()
{
    printf("Please input number:\n");
    scanf("%d",&n);
    Euler();
    printf("%d",mu[n]);
    return 0;
}      

作者：自為風月馬前卒

個人部落格http://attack204.com//

出處：http://zwfymqz.cnblogs.com/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。