最近題讓我非常困惑，貌似我現在已經完全分不清楚哪些題用莫比烏斯反演，哪些用歐拉函數。
下面簡單總結一下，莫比烏斯反演處理的是
- 求segma(gcd(x,y)) 1<=x<=n,1<=y<=m （見《能量項鍊》）
- gcd(x,y) = k 1<=x<=n 1<=y<=m 求x，y對數 （見《bzoj 2301 problem b》）
莫比烏斯反演原來是解決以上問題2的，大體思路是
設F(a,b,k)表示1<=x<=a,1<=y<=b gcd(x,y)|k 對數。
segma(gcd(x,y))== segma(mu[k]*F(n,m,k))
至此事件複雜度O(n)
由於F(n,m,k)=(n/k)*(m/k)，具有一定區間的一致性，於是可以優化爲O(sqrt(n))
在此過程中，需要統計mu[]的前綴和。
而對於問題1，如果枚舉d=gcd(x,y) O(n*sqrt(n))
可以按上文方法，批量d相同的區間即可在將n優化爲sqrt(n)。
歐拉函數題目：
- segma(gcd(i,n)) （見《bzoj 2705》）
- gcd(x,y) = 1，1<=x,y<=n，多重詢問 （見《bzoj 2818》）
歐拉函數的轉換十分靈活，這裏就不一一敘述了。
對比：莫比烏斯反演與歐拉函數
原文：http://www.cnblogs.com/mhy12345/p/4007334.html
