莫比乌斯反演学习记

萌新的莫比乌斯反演学习记。

开头规范

定义单位函数 $\epsilon (n)\begin{cases}1 & n=1\\ 0 & n\neq1 \end{cases}$

定义幂函数 $Id_k(n)=n^k$ 注意 $k$ 取值从 $0$ 开始

定义除数函数 $\sigma_k(n)=\sum_{d|n} \limits d^k$ 注意 $k$ 取值从 $0$ 开始

以及欧拉函数 $\varphi$

迪利克雷卷积

定义数论函数$\mathbb{Z_+} \to \mathbb{C}$ 的函数间的一中二元运算，即：

$(f*g)(n)=\sum_{d|n}\limits f(d)g(\frac{n}{d})$

其中，一个比较重要的性质是若 $f,g$ 是积性函数，那么一定也有 $(f*g)$ 是积性函数。

(似乎只能用 $f*g$ 表示 $f,g$ 的迪利克雷卷积)

一些“常识”

$(f*1)(n)=\sum_{d|n}\limits f(d)1(\frac{n}{d}) =\sum_{d|n}\limits f(d)$

把 $f$ 换成 $Id_k$

$(Id_k*1)(n)=\sum_{d|n}\limits Id_k(d) =\sum_{d|n}\limits d^k=\sigma_k(n)$

对 $\varphi(n),n=p^m$ 有

$(\varphi*1)(n)=\sum_{i=0}^{m}\limits \varphi(p^i) =\sum_{i=1}^{m}\limits (p^i-p^{i-1})+1=n$

否则，因为 $\varphi(n)$ 是积性函数, $\varphi(n)=\sum_{p_{i}^{m}|n}\limits \varphi(p_i^m)=n$

一些性质

交换律，结合律，分配律。

单位元

$(\epsilon *f)(n)=f(n)$ 即 $\epsilon$ 是单位元

逆元

$f*g=\epsilon$ 即 $f^{-1}=g$

同时，有 $f^{-1}(1)=\frac{1}{f(1)}$ 说明 $f(1)\neq 0$

有

$g(n)=\begin{cases}\frac{1}{f(n)}&&n=1 \\ - \frac{1}{f(1)}\sum_{d|n}\limits f(d)g(\frac{n}{d}) &&otherwise \end{cases}$

证明：当 $n\geq 2$ 带入求 $f*g(n)$ 即可

$$\begin{aligned} (f*g)(n)&= \\&=f(1)*g(n)+\sum_{d|n,d \leq 2}\limits f(d)g(\frac{n}{d}) \\&=0 \end{aligned}$$

显然，积性函数都含有逆元。并且，逆元也是积性函数。

莫比乌斯反演

若 $g_n=\sum_{d|n} \limits f(d)$

那么 $f(n)=\sum_{d|n}\limits\mu(d)f(\frac{n}{d})$

其中 $\mu(n)=\begin{cases}1&n=1 \\ (-1)^k &k为n的本质不同的质因子个数\\0& n含有平方因子\end{cases}$

可以证明 $1$ （常数函数）的逆元即为 $\mu(n)$

我们设
$n=\operatorname{\Pi}^{k}{i=1}\limits p{i}^{c_i} ,n’=\operatorname{\Pi}^{k}{i=1}\limits p{i}^{1} $

$\sum_{d|n'}\limits\mu(d)=\sum_{i=0}^{k}C_{k}^{i}$

当且仅当 $\mu(1),\mu(0)$ 为 $1$