luogu 2257 YY的GCD-白红宇

luogu 2257 YY的GCD

阅读量：4358 次

发布时间：2019-06-07

本文共 1223 字，大约阅读时间需要 4 分钟。

题目描述：

给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对。

题解：

代码：

#include
     
      #include
      
       #include
       
        using namespace std;#define N 10000500#define ll long longint pri[N/10],cnt,mu[N];ll f[N],F[N];bool vis[N];void get_mu(){    mu[1]=1;    for(int i=2;i<=10000000;i++)    {        if(!vis[i])        {            pri[++cnt] = i;            mu[i]=-1;        }        for(int j=1;j<=cnt&&1ll*pri[j]*i<=10000000ll;j++)        {            vis[pri[j]*i]=1;            if(i%pri[j])mu[i*pri[j]]=-mu[i];            else            {                mu[i*pri[j]]=0;                break;            }        }    }    for(int i=1;i<=cnt;i++)    {        for(int j=1;j*pri[i]<=10000000;j++)        {            f[j*pri[i]]+=mu[j];        }    }    for(int i=1;i<=10000000;i++)        F[i]=F[i-1]+f[i];}int T,n,m;int main(){    get_mu();    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&n,&m);        ll ans = 0;        int nxt = 1;        for(int i=1;i<=n&&i<=m;i=nxt+1)        {            nxt = min(n/(n/i),m/(m/i));            ans+=(F[nxt]-F[i-1])*(n/i)*(m/i);        }        printf("%lld\n",ans);    }    return 0;}