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

Description

神犇YY虐完数论后给傻×kAc出了一题 给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对 kAc这种傻×必然不会了，于是向你来请教…… 多组输入 Input 第一行一个整数T 表述数据组数 接下来T行，每行两个正整数，表示N, M Output T行，每行一个整数表示第i组数据的结果 Sample Input 2 10 10 100 100 Sample Output 30 2791 HINT T = 10000 N, M <= 10000000 题解： 设p为质数,暴力搞的话显然是

$$\sum_{p}^{}\sum_{d=1}^{\lfloor \frac{n}{p} \rfloor}\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor u(d)$$ 设T=pd,稍微化一下可以变成 $$\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{p|T}^{}u(\frac{T}{p})$$ 设g[t]= ∑p|Tu(Tp) $\sum_{p|T}^{}u(\frac{T}{p})$ 考虑只要求出g数组就可以 n√ $\sqrt n$处理询问了。 g数组可以枚举每个质数然后更新它的倍数. 可以证明这样处理是O(n)的。

#include
   
    #include
    
     #include
     
      #define N 10000010using namespace std;int u[N],p[N],n,m,t,pos;long long g[N],ans;bool f[N];void pre(){  u[1]=1;  for (int i=2;i<=N-10;i++){    if (!f[i]){p[++p[0]]=i;u[i]=-1;}    for (int j=1;j<=p[0]&&i*p[j]<=N-10;j++){      f[i*p[j]]=1;      if (i%p[j]==0){u[i*p[j]]=0;break;}      u[i*p[j]]=-u[i];    }  }  for (int i=1;i<=p[0];i++)   for (int j=1;j<=(N-10)/p[i];j++)     g[p[i]*j]+=(long long)u[j];  for (int i=1;i<=N-10;i++) g[i]+=g[i-1];}int main(){  scanf("%d",&t);pre(); while (t--){  scanf("%d%d",&n,&m);ans=0;  if (n>m) swap(n,m);  for (int i=1;i<=n;i=pos+1){    pos=min(n/(n/i),m/(m/i));    ans+=(long long)(n/i)*(long long)(m/i)*(g[pos]-g[i-1]);   }  printf("%lld\n",ans); }}
     
    
   

转载地址：https://blog.csdn.net/sunshinezff/article/details/50943111 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！