bzoj2820 YY的GCD

bzoj2820 YY的GCD

​​ 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

#include#include#define N 11000000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (S==T){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc(); } return x;}int mu[N],T,not_prime[N],prime[1000000],g[N];int main(){ //freopen("bzoj2820.in","r",stdin); T=read();mu[1]=1;int top=0; for (int i=2;i<=N-1;++i){ if (!not_prime[i]){ mu[i]=-1;prime[++top]=i; }for (int j=1;prime[j]*i<=N-1;++j){ not_prime[i*prime[j]]=true; if (i%prime[j]==0){ mu[i*prime[j]]=0;break; } mu[i*prime[j]]=-mu[i]; } } for(int i=1;i<=top;++i) for (int j=1;j*prime[i]<=N-1;j++) g[j*prime[i]]+=mu[j]; for (int i=1;i<=N-1;++i) g[i]+=g[i-1]; while (T--){ int n=read(),m=read();long long ans=0;int tmp=min(n,m);int last=0; for (int i=1;i<=tmp;i=last+1){ last=min(n/(n/i),m/(m/i)); ans+=(long long)(n/i)*(m/i)*(g[last]-g[i-1]); } printf("%lld\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。