为什么感觉我好像之前学过这玩意- -?
莫比乌斯反演
莫比乌斯反演就是一个能求gcd为多少的个数有几个的东西- -（反正我只知道这么用）
f(x)表示gcd为x的倍数的个数
g(x)表示gcd为x的个数
莫比乌斯反演的基本形式是
f(n) = Σ (g(d)) d | n
g(n) = Σ (g(d) * miu (n / d)) d | n
还有一种形式是
f(n) = Σ (g(d)) n | d
g(n) = Σ (f(d) * miu (d / n)) n | d
其中miu(i)是莫比乌斯函数
莫比乌斯函数
1 (i==1)
miu[i]=-1^k (i为k个不同奇数相乘)
0 (其他情况)
求莫比乌斯函数可以用线性筛法O(n)求出
O(n)求莫比乌斯函数代码
1 void makepri(){ 2 miu[1]=1; 3 for (int i=2;i<N;i++){ 4 if (!bo[i]) pri[++pri[0]]=i,miu[i]=-1; 5 for (int j=1;j<=pri[0] && i*pri[j]<N;j++){ 6 bo[i*pri[j]]=1; 7 if (i%pri[j]==0){ 8 miu[i*pri[j]]=0; 9 break; 10 }else miu[i*pri[j]]=-miu[i]; 11 } 12 } 13 }
优化
用暴力for求g[i]的时间复杂度是O(n)的
但是有的题目会给出很多询问 导致O(n)不能满足出题人- -
假设题目要求gcd(x,y)=1的个数(1<=x<=n,1<=y<=m)
那么f[i]=[n/i]*[m/i]
我们发现[n/i]的值只有√n种 可以按值分块求答案
代码还很短- -
for (int i=1,last=0;i<=n && i<=m;i=last+1){ last=std::min(n/(n/i),m/(m/i)); res+=(sum[last]-sum[i-1])*(n/i)*(m/i); }
原文：http://www.cnblogs.com/g-word/p/3742705.html