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

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。