并不对劲的莫比乌斯反演

很对劲的莫比乌斯反演点这里

重要定理1

(mu(x))是一个定义域为全体正整数的函数，它的定义是：

1.当(x=p_1p_2...p_k)且(p_1p_2...p_k)为互异质数时，(mu(x)=(-1)^k)

2.当(x=1)时，(mu(x)=1)，也可以看成第1种情况中(k=0)时

3.当(x)存在一个质因子幂次大于等于2时，(mu(x)=0)

它的定义听上去很奇怪，但是它有一个非常重要的性质：

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

即当(n=1)时，$$sum_{d|n}mu(d)=1$$当(n eq1)时，$$sum_{d|n}mu(d)=0$$
证明：
设(n=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k})
那么(d)可以看成在这(a_1+a_2+...+a_k)个质数中选择若干个的乘积
发现当(p_1,p_2,...,p_k)中任何一个被选次数超过两次时，(mu(d)=0)，对所有(mu(d))之和没有影响，可以不考虑
那么(d)就变成了在(p_1,p_2,...,p_k)中，每个数至多选一次，选出若干个数的乘积
设选择了(m)个数
当(m)为偶数时，(mu(d)=1)；当(m)为奇数时，(mu(d)=-1)
那么

[sum_{d|n}mu(d)=(sum_{i=0}^{lfloorfrac{k}{2} floor}{C_k^{i*2}})-(sum_{i=0}^{lfloorfrac{k-1}{2} floor}{C_k^{i*2+1}}) ]

设

[f_0(x)=sum_{i=0}^{lfloorfrac{k}{2} floor}{C_k^{i*2}}，f_1(x)=sum_{i=0}^{lfloorfrac{k-1}{2} floor}{C_k^{i*2+1}} ]

则有

[sum_{d|n}mu(d)=f_0(k)-f_1(k) ]

那么问题转化为证明(f_0(k)-f_1(k)=[n=1])
当(n=1)时，(k=0)，(f_0(k)=1,f_1(k)=0)，所以(f_0(k)-f_1(k)=1)
当(n eq1)时，
(1)当(k)为奇数时，(f_0(k)=C_k^0+C_k^2+...+C_k^{k-3}+C_k^{k-1}，f_1(k)=C_k^1+C_k^3+...+C_k^{k-2}+C_k^{k-0})
根据组合数的性质可得(C_k^x=frac{k!}{x!(k-x)!}=C_k^{k-x})
则有(f_0(k)=f_1(k))
(2)当(k)为偶数且不为0时，考虑从(k)个数中去掉一个数
那么没有选被去掉的数且选了偶数个数的方案数和选了被去掉的数且选了奇数个数的方案数是相等的，选了被去掉的数且选了偶数个数的方案数和没有选被去掉的数且选了奇数个数的方案数是相等的
由(1)可得，没有选被去掉的数且选了偶数个数的方案数和没有选被去掉的数且选了奇数个数的方案数是相等的
那么选了被去掉的数且选了偶数个数的方案数和选了被去掉的数且选了奇数个数的方案数也是相等的
所以选了奇数个数的方案数和选了偶数个数的方案数相等，即(f_0(k)=f_1(k))
综上所述，当(n=1)时(f_0(k)-f_1(k)=1)，当(n eq1)时(f_0(k)-f_1(k)=0)，证毕

重要定理2

证完这个结论后就可以得到一个莫反常用的结论：

当$$F(n)=sum_{d|n}f(d)$$时，

有：$$f(n)=sum_{d|n}mu(d)*F(frac{n}{d})$$

证明：

[sum_{d|n}mu(d)*F(frac{n}{d})=sum_{d|n}mu(d)*(sum_{i|frac{n}{d}}f(i)) ]

那么问题转换为算出(f(i)space(i|frac{n}{d}))的系数
设(n=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k})，(d=p_1^{b_1}*p_2^{b_2}*...*p_k^{b_k})，(i=p_1^{c_1}*p_2^{c_2}*...*p_k^{c_k})，则(forall iin[1,k],c_ileq a_i-b_i)
当(b_1,b_2,...,b_k)中存在一个大于1时，(mu(d)=0)，对答案没有贡献，不用考虑
那么(forall iin[1,k],b_ileq min(1,a_i-c_i))
(f(i)space(i|{n}))的系数就是(f_0(Sigma min(1,a_i-c_i))-f_1(Sigma min(1,a_i-c_i)))
当(i=n)时， (forall iin[1,k],c_i=a_i)，(Sigma min(1,a_i-c_i)=0)，(f_0(Sigma min(1,a_i-c_i))-f_1(Sigma min(1,a_i-c_i))=1)，即(f(n))系数为1
当(i eq n)时，(exists iin[1,k],c_i<a_i)，(Sigma min(1,a_i-c_i) eq 0)，(f_0(Sigma min(1,a_i-c_i))-f_1(Sigma min(1,a_i-c_i))=0)，即对于(i eq n)，(f(i))的系数为0
所以，$$sum_{d|n}mu(d)*F(frac{n}{d})=f(n)$$证毕