Description
求有多少对(x,y)的gcd为素数,x<=n,y<=m。n,m<=1e7,T<=1e4。
Solution
因为题目要求gcd为素数的,那么我们就只考虑素数mu的贡献就行了
对于p,对于k*p的贡献是mu[k]
然后加上整除分块优化就行了
p可以筛完素数处理,处理复杂度为O(n/log*log)正好为O(n)
Code
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std; const int maxn=1e7+; int flag[maxn],prime[maxn],mu[maxn],cnt;
ll sum[maxn];
int n,m; void getmu(){
mu[]=;
for(int i=;i<=1e7;i++){
if(!flag[i]){
prime[++cnt]=i;
mu[i]=-;
}
for(int j=;i*prime[j]<=1e7&&j<=cnt;j++){
flag[i*prime[j]]=;
if(i%prime[j]==){
mu[i*prime[j]]=;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
for(int i=;i<=cnt;i++)
for(int j=prime[i];j<=1e7;j+=prime[i])
sum[j]+=mu[j/prime[i]];
for(int i=;i<=1e7;i++)
sum[i]+=sum[i-];
} int main(){
getmu();
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
if(n>m) swap(n,m);
ll ans=;
for(int i=,pos=;i<=n;i=pos+){
pos=min(n/(n/i),m/(m/i));
ans+=(sum[pos]-sum[i-])*(n/i)*(m/i);
}
printf("%lld\n",ans);
}
return ;
}