【莫比乌斯反演】BZOJ2820 YY的GCD

时间:2022-08-29 15:05:11

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 ;
}