莫比乌斯反演

· · 个人记录

莫比乌斯函数

对于莫比乌斯函数\mu(d)，实际上是一个由容斥系数构成的函数，它的定义如下：
当d=1时，\mu (d)=1
当d=\prod\limits_{i=1}^k p_i且p_i为互异素数的时候，\mu (d)=(-1)^k
其他情况下，\mu(d)=0

对于莫比乌斯函数，有以下两个常用的性质：
(1)\sum\limits_{d|n} \mu(d)=[n==1]
(2)\sum\limits_{d|n} \frac{\mu (d)}{d}=\frac{\phi (d)}{n}

同时莫比乌斯函数是一个积性函数，当a与b互质时，有\mu (a\cdot b)=\mu (a)\cdot\mu(b)
所以莫比乌斯函数可以通过线性筛来求得

void get(int maxn)
{
    mu[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!vis[i]) {prime[++cnt]=i;mu[i]=-1;}
        for (int j=1;j<=cnt;j++)
        {
            if (prime[j]*i>maxn) break;
            vis[prime[j]*i]=1;
            if (i%prime[j]==0) break;
            else mu[i*prime[j]]=-mu[i];
        }
    }
}

莫比乌斯反演

设F(n)和f(n)是N_+上的两个函数，且满足

F(n)=\sum\limits_{d|n} f(d)

则有

f(n)=\sum\limits_{d|n} \mu (d) F(\lfloor \frac{n}{d} \rfloor)

上述定理称为莫比乌斯反演定理

证明：

\sum\limits_{d|n} \mu (d) F(\lfloor \frac {n}{d} \rfloor) =\sum\limits_{d|n} \mu (d) \sum\limits_{i|\lfloor \frac {n}{d} \rfloor} f(i) =\sum\limits_{i|n} f(i)\sum_{d|\lfloor \frac{n}{i} \rfloor} \mu (d)=f(n)

当然，莫比乌斯反演还有另外一种形式，当F(n)和f(n)满足

F(n)=\sum\limits_{n|d} f(d)

可以推出

f(n)=\sum\limits_{n|d} \mu (\frac {d}{n}) F(d)