莫比乌斯反演

作者: ffacs 分类: 总结 发布时间: 2020-07-10 16:07

莫比乌斯函数

$$
\begin{equation}
\mu(n)=\left\{
\begin{array}{lr}
1 \qquad\qquad\qquad n=1\\
(-1)^k\qquad\qquad n为k个不同素数的乘积 \\
0\qquad\qquad\qquad 其它
\end{array}
\right.
\end{equation}
$$

性质

$$
\begin{equation}
\sum_{d\mid n}\mu(n)=\left\{
\begin{array}{lr}
1\quad n=1\\
0\quad n>1
\end{array}
\right.
\end{equation}
$$


$$
\sum_{d\mid n}\mu(n)=\left\lfloor\frac{1}{n}\right\rfloor
$$

证明

设 $n=p_1^{a_1}p_2^{a_2}…p_k^{a_k}$ 。当 $k\neq 0$ 时,有
$$
\begin{align}
\sum_{d\mid n}\mu(n)&=\mu(1)+\mu(p_1)+\mu(p_2)…+\mu(p_1p_2)+\mu(p_1p_3)..+\mu(p_1p_2..p_k)+0 \\
&=1+C_k^1(-1)+C_k^2(-1)^2…C_k^k(-1)^k \\
&=(1-1)^k
\end{align}
$$
得证。

莫比乌斯反演

若数论函数 $f(n),g(n)$ 满足
$$
g(n)=\sum\limits_{d\mid n} f(d)
$$

则有

$$
f(n)=\sum\limits_{d\mid n}\mu(d)g(\frac{n}{d})
$$
反之亦成立

证明

$$
\begin{align}
\sum_{d\mid n}\mu(d)g(\frac{n}{d})&=\sum_{d\mid n}\mu(d)\sum_{k\mid \frac{n}{d}} f(k) \\
&=\sum_{k\mid n}f(k)\sum_{d\mid \frac{n}{k}}\mu(d)=f(n)
\end{align}
$$

意义

对于和式中的 $[f=1]$ 我们就可以替换成 $\sum\limits_{d\mid f}\mu(d)$ ,然后通过改变求和次序,数论分块,处理前缀和,来降低和式的复杂度。

发表评论

电子邮件地址不会被公开。 必填项已用*标注