莫比乌斯函数：  

　　Orz  PoPoQQQ

　　

　　这个证明过程第三步和第四步一开始没看懂……

　　第三步：观察计算左边f(k)的系数，可以看出只要d不大于n/k均可以使μ(d)成为f(k)的系数，那么f(k)的系数就是sigma[d丨(n/k)] μ(d) （方括号内为d的范围） 

　　利用整除的性质，重新组合了一下这几项，相当于对一个多项式重新分组提取因式什么的……

　　第四步：利用sigma μ(d)=1或0  那个性质一：当k小于n时，f(k)的系数为0；当k=n时，为1。证毕QAQ

　　向JZJ大神致敬！

 

　　莫比乌斯反演：

　　　　对于一些函数f(n)，如果我们很难直接求出它的值，而容易求出倍数和或约数和F(n)，那么我们可以通过莫比乌斯反演来求得f(n)的值

　　　　例：f(n)表示某一范围内(x,y)=n的数对的数量，F(n)表示某一范围内n|(x,y)的数对的数量

　　　　那么直接求f(n)并不是很好求，而F(n)求起来相对无脑一些，我们可以通过对F(n)进行莫比乌斯反演来求得f(n)

 

　　　　for(i=1;i<=n;i=last+1){

　　　　　　last=min(n/(n/i),m/(m/i));

　　　　　　……

　　　　}

　　　　这种写法可以O(sqrt(n))枚举所有的n/d！这个枚举除法的取值在莫比乌斯反演中非常常用。。？

　　例题：