莫比乌斯函数及莫比乌斯反演

莫比乌斯函数

定义

根据唯一分解定理,\(n=\prod_{i=1}^{k} p_i^{a_i}\)\(\mu\)定义为 \[\mu(n)=\begin{cases}\mu(1)=1\\ \mu(n)=(-1)^k,\quad \forall a_i=1\\ \mu(n)=0,\quad \exists a_i>1\end{cases} \]

性质

  1. \(1\ast \mu=\varepsilon\)\(\sum_{d|n}\mu(d)=\varepsilon(n)\)

    证明:

    \(n=1\)时,显然成立。

    \(n\not=1\)时:

    \[ \begin{aligned}\sum_{d|n}\mu(d) & =\mu(1)+\mu(p_1)+\mu(p_2)+\ldots+\mu(p_k)+\mu(p_1p_2)+\cdots+\mu(p_1p_2\cdots p_k)\\ & =C_{k}^{0}+C_{k}^{1}(-1)+C_{k}^{2}(-1)^2+\cdots+C_{k}^{k}(-1)^k\\ & =\sum_{i=0}^{k}C_{k}^{i}(-1)^i\\ & =(1-1)^k=0\end{aligned} \]

  2. \[\sum_{d|n} \frac{\mu(d)}{d}=\frac{\varphi(n)}{n}\]

求解算法

线性筛

莫比乌斯反演

定义

\[f(n)=\sum_{d|n}g(d)\Leftrightarrow g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})\]\(f=g\ast 1\Leftrightarrow g=f\ast\mu\)

证明

\[f=g\ast 1\Leftrightarrow f\ast\mu=(g\ast 1)\ast\mu\Leftrightarrow f\ast\mu=g\ast(1\ast\mu)\Leftrightarrow f\ast\mu=g\ast\varepsilon\Leftrightarrow f\ast\mu=g\]

应用

  1. 证明\(n=\sum_{d|n}\varphi (d)\)

    由莫比乌斯函数性质2移项,得:\(\varphi(n)=\sum_{d|n}(\mu(d)\frac{n}{d})\)

    \(f(n)=n,g(n)=\varphi(n)\),反演一下,\(n=\sum_{d|n}\varphi (d)\)

作者

xqmmcqs

发布于

2018-01-19

更新于

2021-02-23

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×