莫比乌斯反演

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

开始学习莫比乌斯反演前我们需要一些前置知识：积性函数、Dirichlet卷积、莫比乌斯函数

数论分块与整除相

引理 1

略证

引理 2

表示集合的元素个数

略证

对于，有种取值

对于，有，也只有种取值

数论分块

数论分块的过程大概如下：考虑含有的求和式子（为常数）

对于任意一个，我们需要找到一个最大的，使得

而

略证

即

利用上述结论，我们每次以为一块，分块求和即可

积性函数

定义

若且，则为积性函数。

性质

若和均为积性函数，则以下函数也为积性函数

例子

单位函数：
恒等函数：通常记做
常数函数：
除数函数：通常简记做或，通常简记做
欧拉函数：
莫比乌斯函数：其中表示的本质不同质因子个数，是一个加性函数

Dirichlet卷积

定义

定义两个数论函数的Dirichlet卷积为

性质

Dirichlet卷积满足交换律和结合律

其中为Dirichlet卷积的单位元（任何函数卷都为其本身）

莫比乌斯函数

定义

为莫比乌斯函数

性质

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

含有平方因子 为 的本质不同质因子个数

证明

其中即

设

那么

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

补充结论

反演推论：

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

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

线性筛

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

void getMu() {
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!flg[i]) p[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
            flg[i * p[j]] = 1;
            if (i % p[j] == 0) {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
}

拓展

$（函数即）$

将分解质因数：

首先，因为是积性函数，故只要证明当时成立即可。

因为是质数，于是

易知如下过程

该式子两侧同时卷可得