​

这个文章主要讲一下ACM中1个常用的莫比乌斯反演公式，看到很多博客上面公式是有，但是都没证明，《组合数学》上的证明又没看懂，就自己想了种证明方法，觉得比《组合数学》的证明简单些，就写一下，希望对初学莫比乌斯反演的同学有帮助。

PS：下面公式出现的sigma是累加，另外建议大家看的时候 把公式在纸上写出来！

一：什么是莫比乌斯反演

简单点的说，就是先给出一个函数 F(n) ,然后再由 F(n)定义一个新函数 G(n) 其中   G(n) = sigma(F(d)) (其中d被“包含”于n)   然后 现在我们不知道 F(n)的值 ， 却知道 G(n)， 接着我们就可以通过 反演由G(n)反向得到F(n) 什么叫 (其中d被“包含”于n) ？以及怎么理解反演？ 通过下面的几个例子说明 例1： 我们直接定义 G(n)=sigma(F(i)) (1dm 我们依次确定H(di,n)的值，当我们在确定H(di,n)的值时，前面的值已经确定，即H(dj,n)(jdi且 di|dj 。 假设 H(a,b)==H(1,b/a)对前面的 H(dj,n)和 所有的H(k,m)其中m1) U[x] = 0; -------------------------- 2！！ (6).假设 x 可写成 x = p^e*q  其中p,q为不同质数，e>1 F(x) = U(1)*G(x)+U(q)*G(p^e)+U(p^e)*G(q)+U(x)*G(1) 带入系数后   U(x) = 0; 由此可继续向下递推，得到第二条结论的加强版！！ 如果 x = p^e*z 其中p为质数, z为任意数,e>1  那么  U[x] = 0 ----------------------2！！ 由此，我们得到了 U[x] 的计算方法！！即是U定义中给出的那样！！（没看定义的同学此时再跳回去看吧）

三：应用 得到了公式，也知道了他是怎么来的，现在就用一个应用来加深理解吧  :) 首先我们要给出 第二部分 中那个公式的另外一种形式 = =  我们把它称为形式二吧～ 原式 :  G(n)=sigma(F(d))  (其中n|d,d