不管怎么说 这是很正式的学习莫比乌斯反演。
前置 莫比乌斯反演针对于 数论函数 数论函数：定义域为正整数 陪域为复数的一类函数。
考虑两个数论函数 f(x) g(x) 如果有\(f(n)=\sum_{d|n}{g(d)}\) 那么存在 \(g(n)=\sum_{d|n}{f(\frac{n}{d})\cdot \mu(d)}\)
这就是莫比乌斯反演的一般形式...
进行证明一下吧 先讨论一下\(\mu\)这个有意思的函数 \(\mu(n)\)的值被定义为 n被质因数分解后某一个质因子的指数>=2那么值为0
设质因子个数为k 否则为\((-1)^k\) 特别的 当n==1时 \(\mu(n)=1\)
它还有一个比较好的性质当n>1时\(\sum_{d|n}{\mu(d)}=0\)
关于这个东西的证明 二项式定理显然可以证明出来...
接下来 跟上我们反演的证明。
忘了说 刚才上面的\(f(x)*\mu(x)\)的卷积叫做两个函数的狄利克雷卷积。
还有一个e函数 即狄利克雷卷积的单位元定义为 \(e(n)=[n=1]\) 是不是很显然呢。
因为这显然符合一个函数卷上单位元还等于本身。
此时证明上述反演的正确性.
\(g(n)=\sum_{d|n}{f(\frac{n}{d})\cdot \mu(d)}\) \(f(n)=\sum_{d|n}{g(d)}\)
\(\sum_{d|n}{\mu(d)\cdot f(\frac{n}{d})}=\sum_{d|n}{\mu(d)\sum_{k|\frac{n}{d}}{g(k)}}\)
更改求和顺序则有 \(\sum_{d|n}{\mu(d)\cdot f(\frac{n}{d})}=\sum_{d|n}{g(d)\sum_{k|\frac{n}{d}}{\mu(k)}}\)
那么显然了 \(\sum_{d|n}{\mu(d)\cdot f(\frac{n}{d})}=\sum_{d|n}{g(d)\cdot [\frac{n}{d}=1]}\)
\(\sum_{d|n}{\mu(d)\cdot f(\frac{n}{d})}=g(n)\) 证毕.
这只是初步的内容 以后再慢慢添。
原文：https://www.cnblogs.com/chdy/p/12269995.html