莫比乌斯反演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;
}