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

开始学习莫比乌斯反演前，需要先学习一些前置知识：数论分块、狄利克雷卷积。

为莫比乌斯函数，定义为

详细解释一下：

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

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

即 ，

设

那么

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

这个性质意味着，莫比乌斯函数在狄利克雷生成函数中，等价于黎曼函数 的倒数。所以在狄利克雷卷积中，莫比乌斯函数是常数函数 的逆元。

反演结论：

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

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

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

证明

将 分解质因数：

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

因为 是质数，于是

易知如下过程：

该式子两侧同时卷 可得

设 为两个数论函数。

形式一：如果有 ，那么有 。

这种形式下，数论函数 称为数论函数 的莫比乌斯变换，数论函数 称为数论函数 的莫比乌斯逆变换（反演）。

容易看出，数论函数 的莫比乌斯变换，就是将数论函数 与常数函数 进行狄利克雷卷积。

根据狄利克雷卷积与狄利克雷生成函数的对应关系，数论函数 的莫比乌斯变换对应的狄利克雷生成函数，就是数论函数 的狄利克雷生成函数与黎曼函数 的乘积。

形式二：如果有 ，那么有 。

方法一：对原式做数论变换。

用 来替换 ，再变换求和顺序。最后一步变换的依据：，因此在 时第二个和式的值才为 。此时 ，故原式等价于

方法二：运用卷积。

原问题为：已知 ，证明

易知如下转化：（其中 ）。

对于第二种形式：

类似上面的方法一，我们考虑逆推这个式子。

我们把 表示为 的形式，然后把 的原定义代入式子。

发现枚举 再枚举 的倍数可以转换为直接枚举 的倍数再求出 ，发现后面那一块其实就是 , 整个式子只有在 的时候才能取到值。

求值（多组数据）

根据容斥原理，原式可以分成 块来处理，每一块的式子都为

考虑化简该式子

因为 时对答案才用贡献，于是我们可以将其替换为 （ 当且仅当 时值为 否则为 ），故原式化为

将 函数展开得到

变换求和顺序，先枚举 可得

易知 中 的倍数有 个，故原式化为

很显然，式子可以数论分块求解。

时间复杂度

求值（多组数据）

易得原式即

将原式复制一份并且颠倒顺序，然后将 n 一项单独提出，可得

根据 ，可将原式化为

两个求和式中分母相同的项可以合并。

即

可以将相同的 合并在一起计算，故只需要统计 的个数。当 时，，所以 的个数有 个。

故答案为

变换求和顺序，设 ，合并公因式，式子化为

设 ，已知 为积性函数，于是可以 筛出。每次询问 计算即可。

下面给出这个函数筛法的推导过程：

首先考虑 的值，显然它的约数只有 ，因此

又有 ，则原式可化为

于是有

那么，对于线性筛中的 ，令 ，可得

即

同理有

因此

时间复杂度：

求值（对 取模）

易知原式等价于

枚举最大公因数 ，显然两个数除以 得到的数互质

非常经典的 式子的化法

后半段式子中，出现了互质数对之积的和，为了让式子更简洁就把它拿出来单独计算。于是我们记

接下来对 进行化简。首先枚举约数，并将 表示为

设 ，，显然式子可以变为

观察上式，前半段可以预处理前缀和；后半段又是一个范围内数对之和，记

可以 求解

至此

我们可以 数论分块求解 函数。

在求出 后，回到定义 的地方，可得原式为

可见这又是一个可以数论分块求解的式子！

本题除了推式子比较复杂、代码细节较多之外，是一道很好的莫比乌斯反演练习题！（上述过程中，默认 ）

时间复杂度：（瓶颈为线性筛）

多组数据，求

其中 ， 表示 的约数个数

要推这道题首先要了解 函数的一个特殊性质

再化一下这个式子

将上述式子代回原式

那么 预处理 的前缀和， 分块处理询问，总复杂度 .

结尾补充一个莫比乌斯反演的非卷积形式。

对于数论函数 和完全积性函数 且 ：

我们证明一下

algocode 算法博客