莫比乌斯反演总结

Alioth_ · 2019-02-16 15:28:32 · 个人记录

莫比乌斯反演

其实就是

g(x)=f(x)\times1

f(x)=g(x)/1

只不过乘是狄利克雷卷积除是乘以1的逆即μ

几个常用的函数:

1.\phi(n) 欧拉函数

2.id(n)=n

3.\mu莫比乌斯函数 (1的逆)

4.\epsilon(n)=[n=1]

5.\sigma(n)\ n的约数个数

已知：\epsilon=\mu\times 1 \ \ \ \ \ id=\phi\times 1 \ \ \ \ \ id^k的逆是\mu(n)n^k

两种写法

形式A：

g(x)=\sum\limits_{d|x}{f(d)}

f(x)=\sum\limits_{d|x}{μ(\frac{x}{d})*g(d)}

形式B：

g(x)=\sum\limits_{x|d}^{n}{f(d)}

f(x)=\sum\limits_{x|d}^{n}{μ(\frac{d}{x})*g(d)}

应用

对于一般的题比如让化简一个式子等我们也有两种处理方式

1.直接化简

我们直接提gcd 反演如[gcd(i,j)=1]这个式子然后把用μ表示出的新式子直接带入化简

注意化简\sum时核心是考虑贡献 若内层与外层无关则可以直接提出来若有关则需要计算贡献后提出来即再套上个中括号判断成立条件后提出来有个技巧就是可以改变枚举对象如枚举因数枚举gcd 用换元法替代枚举等

这种情况一般用形式A

2.反演整个式子

这种方法比较巧妙和简单运算量也不高但比较难想

首先令f(x)表示要求的整个式子然后令g(x)等于f(x)*1 对g(x)进行化简然后再用g(x)反演回f(x)

或者有些题不好求出f(x) 但我们可以轻易求出g(x)=\sum\limits_{x|d}^{n}{f(d)}的答案这时候我们再反演回去也可以得到f(x)的值

如P3172选数

题意：求从区间[L,H]（L和H为整数）中选取N个整数，使它们的gcd为K的方案总数模1000000007的值。

这里我们先把L H都除以K 问题就转化为选出几个数使gcd为1 当然可以直接化简但这里可以这样做

令F(i)为选数的gcd为i的倍数的方案总数，则显然 F(i)=(\lfloor\frac{r}{i}\rfloor-\lfloor\frac{l}{i}\rfloor)^N

令f(i)为选数的gcd为i的方案总数，则显然F(i)=\sum\limits_{i|d}f(d)

这里就很巧妙了让形式B的莫比乌斯反演转化到了实际问题上！我们只需反演出f函数即可

两种形式需要看情况选用

几个工具

1.线性筛可以筛积性函数

void pre()//线性筛预处理n^2/3项的前缀和
{ 
    zs[1]=true;//合数 
    mu[1]=phi[1]=1;
    for(int i=2;i<=MAX;++i)
    {
        if(!zs[i])pri[++tot]=i,mu[i]=-1,phi[i]=i-1;
        for(int j=1;j<=tot&&i*pri[j]<=MAX;++j)
        {
            zs[i*pri[j]]=true;
            //这两句判断pri[j]的次数 
            if(i%pri[j])mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];//pri[j]比i中的任何质因子都小 所以pri[j]是i*pri[j]中的最小质因数 
            else{mu[i*pri[j]]=0;phi[i*pri[j]]=phi[i]*pri[j];break;}//找到i的最小质因子pri[j]  如果再往后筛 pri[j]就不是i*pri[j]的最小质因子 有可能在i里 
        }
    }
    for(int i=1;i<=MAX;++i)phi[i]+=phi[i-1];
    for(int i=1;i<=MAX;++i)mu[i]+=mu[i-1];
}

2.杜教筛可以更快速求积性函数前缀和

void pre()//线性筛预处理n^2/3项的前缀和
{ 
    zs[1]=true;//合数 
    mu[1]=phi[1]=1;
    for(int i=2;i<=MAX;++i)
    {
        if(!zs[i])pri[++tot]=i,mu[i]=-1,phi[i]=i-1;
        for(int j=1;j<=tot&&i*pri[j]<=MAX;++j)
        {
            zs[i*pri[j]]=true;
            //这两句判断pri[j]的次数 
            if(i%pri[j])mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];//pri[j]比i中的任何质因子都小 所以pri[j]是i*pri[j]中的最小质因数 
            else{mu[i*pri[j]]=0;phi[i*pri[j]]=phi[i]*pri[j];break;}//找到i的最小质因子pri[j]  如果再往后筛 pri[j]就不是i*pri[j]的最小质因子 有可能在i里 
        }
    }
    for(int i=1;i<=MAX;++i)phi[i]+=phi[i-1];
    for(int i=1;i<=MAX;++i)mu[i]+=mu[i-1];
}
ll Mu(ll x)
{
    if(x<=MAX)return mu[x];//<n^2/3的 
    if(mm[x])return mm[x];//已算好的 
    ll ret=0;
    int i=2,j;
    while(i<=x&&i<2147483647)
    {
        j=x/(x/i);
        ret+=(j-i+1)*Mu(x/i);//数论分块 
        i=j+1;
    }                        
    return mm[x]=1-ret;//记忆化 
}
ll Phi(ll x)
{
    if(x<=MAX)return phi[x];//<n^2/3的 
    if(pp[x])return pp[x];//已算好的 
    ll ret=0;
    int i=2,j;
    while(i<=x&&i<2147483647)
    {                  
        j=x/(x/i);
        ret+=(j-i+1)*Phi(x/i);//数论分块 
        i=j+1;
    }
    return pp[x]=x*(x+1)/2-ret;//记忆化 
}

3.数论分块根据\lfloor\frac{n}{i}\rfloor最多只有\sqrt{n}种情况产生可以化O(n)为O(\sqrt{n})

while(i<=n)
{                  
    j=min(n/(n/i),m/(m/i));
    ans+=n/i*m/i*(sum[j]-sum[i-1]);//数论分块 
    i=j+1;
}

一般套路

先化简然后通过交换求和次序换元等搞出两个积性函数的迪利克雷卷积形式筛出这个函数的前缀和通过数论分块解决

莫比乌斯反演总结