第二道莫比乌斯反演！
这题和HAOI2011的Problem b很像，但是改成了质数……
懒得写题解了:传送门
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int mu[10000005],g[10000005],T,n,m,pri[1000005],cnt,tab[10000005];
void Pre(int n){
mu[1]=1;
for(int i=2;i<=n;i++){
if(!tab[i]){g[i]=1;mu[i]=-1;pri[++cnt]=i;}
for(int j=1;j<=cnt && pri[j]*i<=n;j++){
tab[i*pri[j]]=1;
if(i%pri[j]){mu[i*pri[j]]=-mu[i];g[i*pri[j]]=mu[i]-g[i];}
else {mu[i*pri[j]]=0;g[i*pri[j]]=mu[i];break;}
}
}
for(int i=1;i<=n;i++)tab[i]=tab[i-1]+g[i];
}
long long Solve(long long n,long long m){
if(n>m)swap(n,m);
long long ans=0;
for(int i=1,last;i<=n;i=last+1){
last=min(n/(n/i),m/(m/i));
ans+=(n/i)*(m/i)*(tab[last]-tab[i-1]);
}
return ans;
}
int main(){
freopen("2820.in","r",stdin);
freopen("2820.out","w",stdout);
Pre(10000000);
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
printf("%lld\n",Solve(n,m));
}
return 0;
}
评论 (0)
