//本文同步发布于作业部落
▎什么是莫比乌斯反演? ☞『引入』首先来抛出一个定义，一个随随便便的函数：
F(n)=∑d∣nf(d) F(n)=sum_{d|n}f(d) F(n)=d∣n∑f(d)
fff是个什么玩意的嘞？这个东西不用管，它可以随便理解成一种函数。
d|n是什么呢？就是说F(n)F(n)F(n)等于所有的可以被n整除的d的f(d)f(d)f(d)的总和。
举个例子：
- F(1)=f(1)F(1)=f(1)F(1)=f(1)
- F(2)=f(1)+f(2)F(2)=f(1)+f(2)F(2)=f(1)+f(2)
- F(3)=f(1)+f(3)F(3)=f(1)+f(3)F(3)=f(1)+f(3)
- F(4)=f(1)+f(2)+f(4)F(4)=f(1)+f(2)+f(4)F(4)=f(1)+f(2)+f(4)
- F(5)=f(1)+f(5)F(5)=f(1)+f(5)F(5)=f(1)+f(5)
- F(6)=f(1)+f(2)+f(3)+f(6)F(6)=f(1)+f(2)+f(3)+f(6)F(6)=f(1)+f(2)+f(3)+f(6)
- F(7)=f(1)+f(7)F(7)=f(1)+f(7)F(7)=f(1)+f(7)
- F(8)=f(1)+f(2)+f(4)+f(8)F(8)=f(1)+f(2)+f(4)+f(8)F(8)=f(1)+f(2)+f(4)+f(8)
发现了什么规律？
☞『推导』又上面的一堆东西推出：
- f(1)=F(1)f(1)=F(1)f(1)=F(1)
- f(2)=F(2)−F(1)f(2)=F(2)-F(1)f(2)=F(2)−F(1)
- f(3)=F(3)−F(1)f(3)=F(3)-F(1)f(3)=F(3)−F(1)
- f(4)=F(4)−F(2)f(4)=F(4)-F(2)f(4)=F(4)−F(2)
- f(5)=F(5)−F(1)f(5)=F(5)-F(1)f(5)=F(5)−F(1)
- f(6)=F(6)−F(3)−F(2)−F(1)f(6)=F(6)-F(3)-F(2)-F(1)f(6)=F(6)−F(3)−F(2)−F(1)
- f(7)=F(7)−F(1)f(7)=F(7)-F(1)f(7)=F(7)−F(1)
- f(8)=F(8)−F(4)f(8)=F(8)-F(4)f(8)=F(8)−F(4)
这样规律就越来越明显了。
☞『莫比乌斯反演公式』易得：
F(n)=∑d∣nf(d)=>f(n)=∑d∣nμ(d)F(nd) F(n)=sum_{d|n}f(d) => f(n)=sum_{d|n} mu(d)F( frac{n}{d})F(n)=d∣n∑f(d)=>f(n)=d∣n∑μ(d)F(dn)
其中的μmuμ是莫比乌斯函数。
μmuμ是莫比乌斯函数，这个函数表示起来长这个样：
μ(d)={1d=1(−1)kd=p1+p2+p3+…+pk0others mu(d)=
begin{cases}
1& d=1 \
(-1)^k& d=p_1+p_2+p_3+…+p_k\
0& others
end{cases}
μ(d)=⎩⎪⎨⎪⎧1(−1)k0d=1d=p1+p2+p3+…+pkothers
正因为此，莫比乌斯函数有一个特别的性质。
现在来思考这个东西等于什么：
∑d∣nμ(d)sum_{d|n} mu(d)d∣n∑μ(d)
这玩意儿得分类讨论的。
∑d∣nμ={1n=10n>1sum_{d|n} mu =
begin{cases}
1& n=1\
0& n>1
end{cases}d∣n∑μ={10n=1n>1
为什么呢？证明如下：
- 当n=1时，显然d只有等于1的情况，当d等于1时μ(d)mu(d)μ(d)显然等于1。
- 当n>1时，我们可以试着拆分一下：
- n=p1a1p2a2p2a3……pkakp_1^{a_1} p_2^{a_2} p_2^{a_3} …… p_k^{a_k}p1a1p2a2p2a3……pkak
- 当μ(d)mu(d)μ(d)不等于0时，显然a1,a2,a3,……,aka_1,a_2,a_3,……,a_ka1,a2,a3,……,ak都要等于1。
- 那么我们设质因数个数为r的因子有CkrC_k^rCkr个。
- 根据莫比乌斯函数的取值情况，我们可知：
- ∑d∣n=Ck0−Ck1+Ck2−Ck3+Ck4−Ck5+……+(−1)kCkk=>∑d∣n=∑i=0k(−1)iCkisum_{d|n}=C_k^0-C_k^1+C_k^2-C_k^3+C_k^4-C_k^5+……+(-1)^kC_k^k => sum_{d|n}=sum_{i=0}^k(-1)^iC_k^id∣n∑=Ck0−Ck1+Ck2−Ck3+Ck4−Ck5+……+(−1)kCkk=>d∣n∑=i=0∑k(−1)iCki
- 所以，我们现在的问题就是如何证明∑i=0n(−1)iCni=0sum_{i=0}^n(-1)^iC_n^i=0i=0∑n(−1)iCni=0
- 我们恰好需要用到一个叫做二项式定理的东西。
- 这玩意长这样：(x+y)n=∑i=0nCnixiyn−i(x+y)^n=sum_{i=0}^nC_n^ix^iy^{n-i}(x+y)n=i=0∑nCnixiyn−i
- 当我们将x=-1，y=1代入后就长这样：0=∑i=0n(−1)iCni0=sum_{i=0}^n(-1)^iC_n^i0=i=0∑n(−1)iCni右边完全一样啊，左边等于0。
- 证毕
