莫比乌斯反演常用结论

内容主要来自 oi-wiki

前置知识

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

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

此时 。

显然 ，考虑证明 ：

不妨设 ，考虑证明当 时， 的最大值为 ：

又因为 为整数，所以 。

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

积性函数

定义

若函数 满足 且 都有 ，则 为积性函数。

若函数 满足 且 都有 ，则 为完全积性函数。

性质

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

设 。

若 为积性函数，则有 。

若 为完全积性函数，则有 。

常见数论函数

• 单位函数：（完全积性）
• 恒等函数：， 通常简记作 。（完全积性）
• 常数函数：（完全积性）
• 除数函数：； 通常简记作 或 ， 通常简记作 。
• 欧拉函数：
• 莫比乌斯函数：，其中 表示 的本质不同质因子个数，它也是一个积性函数。

Dirichlet 卷积

定义

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

性质

Dirichlet 卷积满足以下运算规律：

• 交换律 ；
• 结合律 ；
• 分配律 ；
• ，其中 为 Dirichlet 卷积的单位元（任何函数卷 都为其本身）

例子

莫比乌斯函数

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

即 ，

莫比乌斯反演

公式

设 为两个数论函数。

如果有 ，那么有 。

如果有 ，那么有 。

证明

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

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

方法二：运用卷积。

原问题为：已知 ，证明

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