莫比乌斯反演

和 是定义在非负整数集合上的两个函数，并且满足条件 。那么，我们得到结论：

证：

莫比乌斯函数

在上面的公式中有一个莫比乌斯函数 ，它的定义如下：

1. 若 ，那么
2. 若 ， 均为互异素数，那么
3. 其他情况下

性质

对于 函数，它有如下的常见性质：

1. 设 表示 n 的质因子个数， 对任意正整数 n 有：

证：

2. 对任意正整数 n 有：

证：

用线性筛选求莫比乌斯反演函数的代码：

int init(int n) {
    int tot = 0;
    for(int i = 1; i <= n; ++ i) vis[i] = 0;
    for(long long i = 2; i <= n; ++ i) {
        if (!vis[i]) prime[++tot] = i, mu[i] = -1;
        for(int j = 1; i * prime[j] <= n; ++ j) {
            vis[i*prime[j]] = 1;
            if (i % prime[j] == 0) break;
            else mu[i*prime[j]] = -mu[i];
        }
    }
    return tot;
}