数学-数论-莫比乌斯函数及莫比乌斯反演

Posted by

莫比乌斯函数

定义

根据唯一分解定理,\(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)\)。

3 comments

Leave a Reply

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