发布于 ,更新于 

莫比乌斯反演

请先去初等数论学习一些常用记号。

莫比乌斯函数

\(\mu(n)\)

  • \(\mu(1)=1\)
  • \(n\) 进行质因数分解:
    • 分解后有相同的质因数:\(\mu(n) = 0\)
    • 分解后无相同的质因数,有 \(k\) 个不同的质因数:\(\mu(n)=(-1)^k\)

性质

  • \(n\in\mathbb{N^*},\sum_{d\mid n}\mu(d) = [n=1]\)

莫比乌斯反演

若有 \(g(n) = \sum_{d\mid n} f(d)\),则有 \(f(n) = \sum_{d\mid n} f(d)\mu(\frac nd)\)

显然是狄利克雷卷积形式啊,所以可以简化一下。

\[ g(n) = \sum_{d\mid n} f(d) \to f = g * \mu \]

证明

我们知道,莫比乌斯函数有一个性质:\(n\in\mathbb{N^*},\sum_{d\mid n}\mu(d) = [n=1]\),换成狄利克雷卷积的形式即是 \(\mu * I = \epsilon\)

然后开始证明:

已知:

\[ g(n) = \sum _{d\mid n}f(d) \]

换成狄利克雷卷积形式,再在两边同时卷一个 \(\mu\)

\[ \begin{aligned} g &= f * I \newline g * \mu &= f * I * \mu \end{aligned} \]

利用结合律和上面的性质就可以证明完成了。

\[ \begin{aligned} g * \mu &= f * (I * \mu) \newline g * \mu &= f * \epsilon \newline g * \mu &= f \end{aligned} \]