2820: YY的GCD Time Limit: 10 Sec Memory Limit: 512 MB Submit: 1951 Solved: 1036 [Submit][Status][Discuss] 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
【分析】 我发现我的数学只会暴力求gcd，哦艹
参见PoPoQQQ的ppt或者hzwer的代码吧
【代码】
//bzoj 2820 YY的GCD #include<iostream> #include<cstring> #include<cstdio> #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=10000005; bool vis[mxn]; int prm[mxn],miu[mxn]; ll sum[mxn]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); return x*f; } inline void init() { int i,j; miu[1]=1; fo(i,2,mxn-5) { if(!vis[i]) prm[++prm[0]]=i,miu[i]=-1; fo(j,1,prm[0]) { if(i*prm[j]>mxn-5) break; vis[i*prm[j]]=1; if(i%prm[j]==0) break; miu[i*prm[j]]=-miu[i]; } } fo(i,1,prm[0]) //暴力枚举素数 for(j=1;j*prm[i]<=mxn-5;j++) sum[j*prm[i]]+=miu[j]; fo(i,1,mxn-5) sum[i]+=sum[i-1]; } inline ll solve(int n,int m) { ll tot=0; for(int i=1,last=0;i<=n;i=last+1) { last=min(n/(n/i),m/(m/i)); tot+=(sum[last]-sum[i-1])*(n/i)*(m/i); } return tot; } int main() { int i,j,k,n,m,T; init(); T=read(); while(T--) { n=read(),m=read(); if(n>m) swap(n,m); printf("%lld\n",solve(n,m)); } return 0; }