莫比乌斯反演是一种非常实用而且装逼的算法，它以容斥为基础，来解决一些复杂的数学问题。

先给出莫比乌斯反演的公式：

设定义在自然数集合中的两个函数 $F(x)$ 和 $f(x)$，若这两个函数满足条件：

$$F(n)=\sum_{d|n}f(d)$$

那么则会有：

$f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})$

其中 $\mu$ 为莫比乌斯函数，可以在我的这篇文章中了解关于莫比乌斯函数的知识。

下面我们来证明这个公式。

首先需要了解狄利克雷卷积的一些性质（注：以下出现的函数都是定义在自然数集合上的）：

设 $*$ 为狄利克雷卷积。

若有两个函数 $f$ 和 $g$，且 $f=g$，那么就有：$f * h=g * h$，其中，$h​$ 为另一个函数。

对于三个函数 $f​$、$g​$、$h​$，则会有 $f * (g * h) = (f * g) * h​$。

以上就是需要了解的知识。

$\because F(n)=\sum_{d|n}f(d)​$

$\therefore F=f*I$（$I$ 为不变函数，此函数的值恒为 $1$）

$\therefore F * \mu = f * I * \mu$

$\because I * \mu = \epsilon​$（$\epsilon​$ 为原函数，$\epsilon(n) = [n = 1]​$）

$\therefore F * \mu = f * \epsilon$

又 $\because f * \epsilon = f$

$\therefore F*\mu=f​$

$\therefore f(n)=\sum_{d|n}\mu(d) F(\frac{n}{d})$

Q.E.D

对于一些莫比乌斯反演的题，千万别忘了一个重要的东西：

$$\mu * I=\epsilon$$

这个等式在推柿子中很有用，所以一定要记住。我就是因为忘了这个所以有好长一段时间不理解大多数式子是怎么推出来的

举个例子：

求：

$$\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=1]​$$

那么这个柿子就可以这么推：

$$\begin{align}\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=1] &= \sum_{i=1}^n \sum_{j=1}^m \epsilon(\gcd(i,j)) \\\\ &= \sum_{i=1}^n \sum_{j=1}^m \mu*I \\\\ &= \sum_{i=1}^n \sum_{j=1}^m \sum_{d|\gcd(i,j)}\mu(d) \\\\ &= \sum_{i=1}^n \sum_{j=1}^m \sum_{d|i} \sum_{d|j} \mu(d) \\\\\ &=\sum_{d=1}^n \mu(d) \sum_{i=1}^n \sum_{d|i} \sum_{j=1}^n \sum_{d|j} 1 \\\\ &= \sum_{d=1} \mu(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \end{align}$$

接下来是一些关于莫比乌斯反演的练习题：

[SDOI2015]约数个数和

[POI2007]ZAP-Queries

YY的GCD

如果有什么讲解错误，请在下面的评论中指出（毕竟百密一疏）