大意
给定多组(N)，(M)，求(1le xle N,1le yle M)并且(Gcd(x, y))为质数的((x, y))有多少对。
思路
我们设(f(i))表示(Gcd(x,y)=i)的((x,y))的个数，(F(i))表示(Gcd(x,y)\%i=0)的((x,y))的个数。
那么有$$F(i)=lfloorfrac{N}{i}
floorlfloorfrac{M}{i}
floor=sum_{imid d}f(d)$$，
用莫比乌斯反演得到：$$f(i)=sum_{imid d}mu(frac{d}{i})cdot F(d)$$
那么我们要求的(Ans)就为：$$Ans=sum_{pin prime}f[p]=sum_{pin prime}sum_{pmid d}mu(frac{d}{p})cdot F(d)$$
即$$Ans=sum_{pin prime}sum_{pmid d}mu(frac{d}{p})cdot lfloorfrac{N}{d}
floorlfloorfrac{M}{d}
floor$$
上述化简式对于单组数据已经够了，然而，对于多组数据依然有较大的缺陷，考虑优化。
对上述式子变形：$$Ans=sum_{d=1}^{min(N,M)}lfloorfrac{N}{d}
floorlfloorfrac{M}{d}
floorcdot(sum_{pin prime&pmid d}mu(frac{d}{p}))$$
对于后面的式子，我们可以预先处理好对于每个(d)的总和，然后发现前面为一个数论分块，所以可以(O(Tsqrt{N}))算。
代码
#include<cstdio>
#include<algorithm>
using namespace std;
const long long ONE=1;
const int MAXV=10000000;
const int MAXN=10000005;
int T,A,B,Miu[MAXN];
long long Sum[MAXN];
int Pcnt,Prime[MAXN],visp[MAXN];
long long Ans;
void Prepare(){
visp[0]=visp[1]=1;Miu[1]=1;
for(int i=2;i<=MAXV;i++){
if(!visp[i]){Prime[++Pcnt]=i;Miu[i]=-1;}
for(int j=1;j<=Pcnt&&i*Prime[j]<=MAXV;j++){
visp[i*Prime[j]]=1;
if(i%Prime[j]==0){
Miu[i*Prime[j]]=0;
break;
}
else Miu[i*Prime[j]]=-Miu[i];
}
}
for(int i=1;i<=Pcnt;i++)
for(int j=1;j*Prime[i]<=MAXV;j++)
Sum[j*Prime[i]]+=Miu[j];
for(int i=1;i<=MAXV;i++)
Sum[i]=Sum[i-1]+Sum[i];
}
int main(){
Prepare();
scanf("%d",&T);
while(T--){Ans=0;
scanf("%d%d",&A,&B);
int lowin=min(A,B);
for(int L=1,R;L<=lowin;L=R+1){
R=min(A/(A/L),B/(B/L));
Ans+=(Sum[R]-Sum[L-1])*(A/L)*(B/L);
}
printf("%lld
",Ans);
}
}