莫比乌斯反演 学习笔记

注：以下内容源自各种各样的资料，不保证正确性，仅供参考。

约定 $*$ 代表运算“卷”，部分出现的 $1$ 代表常数函数。

莫比乌斯函数

$\mu$ 为莫比乌斯函数，定义为：
$$
\mu(n)=\begin{cases}
1 & n=1 \
0 & n\text{含有平方因子}\
(-1)^k & k\text{为}n\text{的本质不同质因子个数}
\end{cases}
$$
莫比乌斯函数是积性函数，可以求线性筛的同时求出。

莫比乌斯函数的性质

• 性质1：
  $$
  \sum\limits_{d|n}\mu (d)=\begin{cases}
  1 & n=1 \
  0 & n\neq 1
  \end{cases}
  $$
  也就是说，$\sum_{d|n}\mu(d)=\varepsilon(n)$，即 $\mu * 1=\varepsilon$

  • 引理：$[gcd(i,j)=1]=\sum\limits_{d|gcd(i,j)}\mu(d)$

• 性质2：
  $$
  \varphi * 1=\operatorname{id}
  $$
  两边同时卷 $\mu$ 可得到 $\varphi=\operatorname{id}*\mu$

莫比乌斯变换与反演

设 $f(n),g(n)$ 是两个数论函数。

• 如果有 $f(n)=\sum_{d|n}g(d)$，那么有 $g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})$

  这种形式下，$f(n)$ 称作 $g(n)$ 的莫比乌斯变换，$g(n)$ 称作 $f(n)$ 的莫比乌斯反演。

• 如果有 $f(n)=\sum_{n|d}g(d)$，那么有 $g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)$

应用

莫反常常与数论分块+前缀和结合，加速运算。