Alioth_ 的博客

Alioth_ 的博客

莫比乌斯反演总结

posted on 2019-02-16 15:28:32 | under 知识点 |

莫比乌斯反演

其实就是

$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;
}

一般套路

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