莫比乌斯反演总结

终于弄明白莫比乌斯反演是怎么回事了，来总结一下...

首先是莫比乌斯函数的定义

， p1，p2，p3，...，pk为互不相等的素数

莫比乌斯函数有一个很重要的性质：

， [m = 1]的意思是， m等于1时，结果为1，否则，结果为0

证明如下：

根据唯一分解定理，任何一个大于1的自然数 N，如果N不为素数，那么N可以唯一分解成有限个素数的乘积，

那么枚举m的约数d，也就是将m唯一分解，然后枚举它的素因子的组合，根据莫比乌斯函数的定义，当d由奇数个互不相等的素因子组成时，

u(d) = -1，当d由偶数个互不相等的素因子组成时，u(d) = 1.

将m唯一分解，m = p1p2p3...pn，那么只要证明从n个不同的数中选取奇数个数和选取偶数个数（0个也算偶数个）的方法数相等就证明了这个性质

根据二项式定理，有

n为奇数时，

n为偶数时，

所以，从n个不同的数中选取奇数个数和选取偶数个数（0个也算偶数个）的方法数相等，这样莫比乌斯函数的这个性质也就被证明了。

然后是莫比乌斯反演：

已知，求f(m)

答案是：

当g(m)比较好求，时间复杂度比较低，而f(m)比较难求，时间复杂度比较高的时候，可以用莫比乌斯反演来简化运算，

或者已知g(m)求f(m)的时候，可以用莫比乌斯反演

要证明莫比乌斯反演需要用到两条重要的性质：

①，这个很容易理解，就是把枚举m的约数d的顺序变了一下，

②，这个我现在还不会证明，等会了以后再放上来

有了这两个性质，就可以证明莫比乌斯反演了，证明如下：

莫比乌斯函数筛法：

void init() {
    memset(vis, 0, sizeof vis);
    mu[1] = 1; len = 0;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) {
            pri[len++] = i;
            mu[i] = -1;
        }
        for (int j = 0; j < len && i * pri[j] < maxn; ++j) {
            vis[i * pri[j]] = 1;
            if (i % pri[j]) mu[i * pri[j]] = -mu[i];
            else {
                mu[i * pri[j]] = 0;
                break;
            }
        }
    }
}