引

如果有要学习莫比乌斯反演的同学请看这里：【算法】莫比乌斯反演 -boshi

因为本文只是讲一下个人对于莫比乌斯函数的理解的，并不会讲莫比乌斯反演。

（顺带一提我在半年前就学了莫比乌斯反演并象征性地刷了几道模板题。。。但是我直到昨天才真的搞懂了这玩意。。。）

下面开始口胡，不要吊打我啊 QvQ

莫比乌斯反演

我们先来复习一下

假设对于数论函数 $f(n)$和 $F(n)$，有以下关系式：

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

则将其默比乌斯反转公式定义为：

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

莫比乌斯函数

$$
\mu (n)=
\begin{cases}
1 &若 n = 1\\
(-1)^k &若 n 无平方因数，即 n=p_1p_2…p_k\\
0 &若 n 有大于 1 的平方数因数\\
\end{cases}
$$

拿上面那个莫比乌斯反演公式来说，我们可以这样表示 $F(1)…F(8)$：

$
F(1)=f(1)\\
F(2)=f(1)+f(2)\\
F(3)=f(1)+f(3)\\
F(4)=f(1)+f(2)+f(4)\\
F(5)=f(1)+f(5)\\
F(6)=f(1)+f(2)+f(3)+f(6)\\
F(7)=f(1)+f(7)\\
F(8)=f(1)+f(2)+f(4)+f(8)\\
$

利用解方程，我们得到：

$
f(1)=F(1)\\
f(2)=F(2)-F(1)\\
f(3)=F(3)-F(1)\\
f(4)=F(4)-F(2)\\
f(5)=F(5)-F(1)\\
f(6)=F(6)-F(3)-F(2)+F(1)\\
f(7)=F(7)-F(1)\\
f(8)=F(8)-F(4)\\
$

观察发现我们可以把 $f(n)$表示成一堆 $F(d)$相加相减的形式。

于是我们想到可以用一个函数来表示对于一个 $F(d)$我们是要加还是减。

设这个函数为 $\mu(n)$

对于要加的 $F(d)$，它对应的 $\mu$的函数值为 $1$。

对于要减的 $F(d)$，它对应的 $\mu$的函数值为 $-1$。

对于不加也不减的 $F(d)$，它对应的 $\mu$的函数值为 $0$。

然后我们可以思考一下，若我们要求 $f(n)$的值，那么 $F(n)$对应的 $\mu$必须等于 $1$，为了实现这一点，我们将计算 $F(d)$对应的莫比乌斯函数设为 $\mu(\frac{n}{d})$，这样 $F(n)$对应的就是 $\mu(1)$，我们将 $\mu(1)$设为 $1$

再看下这个求 $f(n)$的式子：

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

现在我们进行分类讨论（后文 $p$表示质数）：

对于 $n=1$

$
F(1)=f(1)\\
f(1)=F(1)\\
$

即 $\mu(1)=1$

对于 $n=p$

$
F(p)=f(1)+f(p)\\
f(p)=F(p)-f(1)\\
f(p)=F(p)-F(1)\\
$

其中 $F(1)$对应的系数是 $-1$，即 $\mu(p)=-1$

对于 $n=p^2$

$
F(p^2)=f(p^2)+f(p)+f(1)\\
f(p^2)=F(p^2)-f(p)-f(1)\\
f(p^2)=F(p^2)-F(p)\\
$

其中 $F(1)$对应的系数是 $0$（不存在这个项），即 $\mu(p^2)=0$

对于 $n=p^k$

当然这里的 $k$是大于 $1$的 =。=

对于 $n=3$的情况：

$
F(p^3)=f(p^3)+f(p^2)+f(p)+f(1)
f(p^3)=F(p^3)-f(p^2)-f(p)-f(1)
f(p^3)=F(p^3)-F(p^2)
$

于是我们又得到了 $\mu(p^3)=0$

然后根据数学归纳法：
$
f(p^k)=F(p^k)-F(p^{k-1})
$

即 $\mu(p^k)=0$

对于 $n=p_1\cdot p_2$

$
F(p_1\cdot p_2)=f(p_1\cdot p_2)+f(p_1)+f(p_2)+f(1)\\
f(p_1\cdot p_2)=F(p_1\cdot p_2)-f(p_1)-f(p_2)-f(1)\\
f(p_1\cdot p_2)=F(p_1\cdot p_2)-F(p_1)-F(p_2)+F(1)\\
$

即 $\mu(p_1\cdot p_2)=1$

对于 $n=p_1\cdot p_2\cdot …\cdot p_k$

对于 $k=3$的情况：

$$
\begin{aligned}
F(p_1\cdot p_2\cdot p_3)=&f(p_1\cdot p_2\cdot p_3)+f(p_1\cdot p_2)+f(p_2\cdot p_3)+f(p_3\cdot p_1)+f(p_1)+f(p_2)+f(p_3)+f(1)\\
f(p_1\cdot p_2\cdot p_3)=&F(p_1\cdot p_2\cdot p_3)-f(p_1\cdot p_2)-f(p_2\cdot p_3)-f(p_3\cdot p_1)-f(p_1)-f(p_2)-f(p_3)-f(1)\\
f(p_1\cdot p_2\cdot p_3)=&
F(p_1\cdot p_2\cdot p_3)-[F(p_1\cdot p_2)-F(p_1)-F(p_2)+F(1)]-[F(p_2\cdot p_3)-F(p_2)-F(p_3)+F(1)]-\\&
[F(p_3\cdot p_1)-F(p_3)-F(p_1)+F(1)]-[F(p_1)-F(1)]-[F(p_2)-F(1)]-[F(p_3)-F(1)]-F(1)\\
\end{aligned}
$$

好的上式太长了我们就不展开了，因为我们只关心 $F(1)$前面的系数，所以我们省略掉其它无关的部分：

$
f(p_1\cdot p_2\cdot p_3)=…-F(1)-F(1)-F(1)+F(1)+F(1)+F(1)-F(1)
f(p_1\cdot p_2\cdot p_3)=…-F(1)
$

即 $\mu(p_1\cdot p_2\cdot p_3)=-1$

我们来研究一下为什么对于 $k=2$时 $\mu(p_1\cdot p_2)=1$而对于 $k=3$时 $\mu(p_1\cdot p_2\cdot p_3)=-1$

我们先设 $g(k)$表示 $\mu(p_1\cdot p_2\cdot …\cdot p_k)$的值

已知：$g(1)=-1,g(2)=1,g(3)=-1$

对于 $n=p_1\cdot p_2\cdot p_3\cdot p_4$：

• $f(4)$减去了 $C_4^1=4$个 $g(1)$，即 $-4\times -1=4$
• $f(4)$减去了 $C_4^2=6$个 $g(2)$，即 $-6\times 1=-6$
• $f(4)$减去了 $C_4^3=4$个 $g(3)$，即 $-4\times -1=4$
• $f(4)$本身定义式中移项后就减去了 $1$个 $F(1)$

总和上面的：$g(4)=4-6+4-1=1$

然后根据数学归纳法我们知道或相信：

$$
g(n)=
\begin{cases}
-1 & n 为奇数\\
1 & n 为偶数\\
\end{cases}
$$

对于 $n=p_1^i\cdot p_2\cdot …\cdot p_k$

先来看对于 $i=2,k=2$的情况：

$
F(p_1^2\cdot p_2)=f(p_1^2\cdot p_2)+f(p_1^2)+f(p_1)+f(p_1\cdot p_2)+f(p_2)+f(1)\\
f(p_1^2\cdot p_2)=F(p_1^2\cdot p_2)-f(p_1^2)-f(p_1)-f(p_1\cdot p_2)-f(p_2)-f(1)\\
f(p_1^2\cdot p_2)=F(p_1^2\cdot p_2)-f(p_1^2)-[f(p_1)+f(p_1\cdot p_2)+f(p_2)+f(1)]\\
f(p_1^2\cdot p_2)=F(p_1^2\cdot p_2)-F(p_1^2)+F(p_1)-F(p_1\cdot p_2)\\
$

即 $\mu(p_1^2\cdot p_2)=0$

那对于 $i>2,k>2$的情况呢？亦或是次数大于 $1$的 $p$不止 $1$个呢？

依然是数学归纳 QvQ

你每次可以把形似 $f(p^i)$的式子提出来，然后像上面一样分解，于是你就会发现式子中形似 $f(p_1^i\cdot p_2\cdot …\cdot p_k)$的项的规模变小了。。。

好吧也许证明这个我们需要用到 $\mu(n)$是个积性函数。

后记

好吧证明真的很不严谨。

希望大家能够理解啊 QvQ