莫比乌斯反演

引入#

莫比乌斯反演是数论中的重要内容。对于一些函数 ，如果很难直接求出它的值，而容易求出其倍数和或约数和 ，那么可以通过莫比乌斯反演简化运算，求得 的值。

定义#

为莫比乌斯函数，定义为

详细解释一下：

令 ，其中 为质因子，。上述定义表示：

1. 时，；
2. 对于 时：
   1. 当存在 ，使得 时，，也就是说只要某个质因子出现的次数超过一次， 就等于 ；
   2. 当任意 ，都有 时，，也就是说每个质因子都仅仅只出现过一次时，即 ， 中个元素唯一时， 等于 的 次幂，此处 指的便是仅仅只出现过一次的质因子的总个数。

性质#

莫比乌斯函数不仅是积性函数，还有如下性质：

即 ，

{% label 重要的转换方式: blue %} 如果有,则有.
如果有,则有.

证明#

设

那么

根据二项式定理，易知该式子的值在 即 时值为 否则为 ，这也同时证明了 以及

所以在狄利克雷卷积中，莫比乌斯函数是常数函数 的逆元。

补充结论#

反演结论：

直接推导：如果看懂了上一个结论，这个结论稍加思考便可以推出：如果 的话，那么代表着我们按上个结论中枚举的那个 是 ，也就是式子的值是 ，反之，有一个与 相同的值：

利用 函数：根据上一结论，，将 展开即可。

线性筛#

由于 函数为积性函数，因此可以线性筛莫比乌斯函数（线性筛基本可以求所有的积性函数，尽管方法不尽相同）。

int pri[50005],mu[50005],tot;
bool vis[50005];
void get_mu(int n){
    mu[1]=1;//注意初始化
    for(int i = 2;i<=n;i++){
        if(!vis[i]){
            pri[++tot]=i;
            mu[i]=-1;//是质数
        }
        for(int j = 1;i*pri[j]<=n&&j<=tot;j++){
            int m=i*pri[j];
            vis[m]=1;
            if(i%pri[j]==0){
                mu[m]=0;//有平方因子
                break;
            }
            mu[m]=-mu[i];
        }
    }
}