【莫比乌斯反演】[BZOJ 2820 YY的GCD]

从黄学长那盗来的图

可以线筛预处理F,或者暴力枚举质数（这个复杂度我不能确定）,按照素数粗略个数n/logn以及调和级数求和nlogn来看暴力的复杂度接近On 处理完F以后就是喜闻乐见的下底函数分块

n,m;int no[maxl],p[maxl],mu[maxl];long long sum[maxl];long long ans;void shai(){no[1]=1;mu[1]=1;for(int i=2;i<maxl;i++){if(!no[i])p[++p[0]]=i,mu[i]=-1;int j=1,t=p[1]*i;while(j<=p[0] && t<maxl){no[t]=1;if(i%p[j]==0){mu[t]=0;break;}mu[t]=-mu[i];t=i*p[++j];}}for(int i=1;i<=p[0];i++){int num=p[i];for(int j=1;j*num<maxl;j++)sum[j*num]+=mu[j];}for(int i=1;i<maxl;i++)sum[i]+=sum[i-1];}void prework(){scanf(“%d%d”,&n,&m);if(n>m){int t=n;n=m;m=t;}}){if(x<y)return x;;}void mainwork(){int pos=0;ans=0;for(int i=1;i<=n;i=pos+1){pos=min((n/(n/i)),(m/(m/i)));ans+=(sum[pos]-sum[i-1])*(n/i)*(m/i);}}void print(){printf(“%lld\n”,ans);}int main(){int t;shai();scanf(“%d”,&t);while(t–){prework();mainwork();print();}return 0;}

，在时光的激流中，我们总会长大。