扯dan

最近又复习（学习）了有关莫比乌斯反演的内容，对反演的原理以及作用有了更加深刻的理解，于是写一篇博客记录一下。

莫比乌斯反演

这里直接进入正题。 给出下面这个形式的公式

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

对于这个公式，有一个结论：如果f(d) 让g(n)是积性函数。那么f(d) 是积性函数。（这个结论证明这里并不给出亲自行证明（我会说是我太懒吗？））这个结论挺重要的，但我们要讲内容主要是反演。 我们考虑如何用$g(n)$来表示$f(n)$，有这样一个反演原理（具体怎么来的，额……）：

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

后面我们会简单的证明该原理。 $\mu(d)$就是我们熟悉的懵逼（莫比）乌斯函数了，对于莫比乌斯函数有一个重要的性质（好多大神都叫它推论）：

$$\sum_{d|n}\mu(d)=[n==1]$$

右边的是bool表达式，当n=1时为1否则为0。参考大神的博客，说这个性质正是构造出来的，使得反演成立。 除了这个性质，在证明原理前我们还要知道以下两点：

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

这个很显然，不过是反过来统计。 这一点比较难懂（其实并没有，只是我当时认识比较繁琐）

$$\sum_{d|n}\mu(\frac{n}{d})\sum_{d'|d}{f(d')}=\sum_{d'|n}{f(d')}\sum_{d| \frac{n}{d'}}{\mu(d)} \tag{2}$$

这个式子看上去复杂，但实际上是相当简（fu）单（za）的。我们先假设$n=p$，$p$是一个质数。 那左边是：

$$\mu(p)f(1)+$$

$$\mu(1)f(1)+\mu(1)f(p)$$

右边：

$$f(1)\mu(1)+f(1)\mu(p)+$$

$$f(p)\mu(1)$$

显然相等
我们在假设$n=pq$，$p$和$q$均为质数。
左边：

$$\mu(n)f(1)+$$

$$\mu(q)f(1)+\mu(q)f(p)+$$

$$\mu(p)f(1)+\mu(p)f(q)+$$

$$\mu(1)f(1)+\mu(1)f(p)+\mu(1)f(q)+\mu(1)f(n)$$

右边：

$$f(1)\mu(1)+f(1)\mu(p)+f(1)\mu(q)+f(1)\mu(n)+$$

$$f(p)\mu(1)+f(p)\mu(q)+$$

$$f(q)\mu(1)+f(q)\mu(p)+$$

$$f(n)\mu(1)$$

任然相等。 所以对于$n=pq\cdots$我们都可以用相同的方法。 我们开始证明：
对于

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

有

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

证明：

$$\sum_{d|n} {\mu(d)g(\frac{n}{d})}=\sum_{d|n} {\mu(\frac{n}{d})g(d)}$$

$$\sum_{d|n} {\mu(\frac{n}{d})g(d)}=\sum_{d|n}{\mu(\frac{n}{d})\sum_{d'|d}f(d')}$$

$$\sum_{d|n}{\mu(\frac{n}{d})\sum_{d'|d}f(d')}=\sum_{d'|n}{f(d')}\sum_{d| \frac{n}{d'}}{\mu(d)}$$

$$\sum_{d'|n}{f(d')}\sum_{d| \frac{n}{d'}}{\mu(d)}=\sum_{d'|n}{f(d')}[\frac{n}{d'}==1]$$

$$\sum_{d'|n}{f(d')}[\frac{n}{d'}==1]=f(n)$$

证毕。

我对反演的理解大致如此。

水平有限，讲得不好，如有错误，还请指出，不胜感激。