Gcd
Time Limit: 10 Sec Memory Limit: 256 MBDescription
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
Input
一个整数N
Output
如题
Sample Input
4
Sample Output
4
HINT
hint
对于样例(2,2),(2,4),(3,3),(4,2)1<=N<=10^7
题解：根据题意，我们要求求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对。
显然我们不可能将1到N的所有数对都枚举一遍，现在考虑枚举所有质数。
因为gcd(a,b)==p(p为质数),所以gcd(a/p,b/p)==1;
那么我们只要枚举所有小于N的质数，然后找⌊a/p⌋和⌊b/p⌋互质的对数。
显然只要先预处理出欧拉函数，然后用一层循环枚举1~⌊a/p⌋统计一下和就可以了。
注意一下几点：
1.每次统计都要乘上2，因为反过来也算一个数对。比如样例中2,4和4,2是不同的数对。
2.每次统计完之后ans-- 因为每次统计都乘2必然会有一个包含两个相同数的数对被多计算一次，比如样例中2,2和3,3都被计算了两次，所以要被减掉。
3.至于怎么筛质数，欧拉函数，以及高端大气上档次的莫比乌斯函数，实际上可以同时做到。
void find_prime(int listsize){ int i,j; memset(isprime,1,sizeof(isprime)); isprime[1]=false; phi[1]=1; mu[1]=1; for(i=2;i<=listsize;i++) { if(isprime[i]) { prime[++primesize]=i; phi[i]=i-1; mu[i]=-1; } for(j=1;j<=primesize&&i*prime[j]<=listsize;j++) { isprime[i*prime[j]]=false; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; mu[i*prime[j]]=0; break; } else { phi[i*prime[j]]=phi[i]*(prime[j]-1); mu[i*prime[j]]=-mu[i]; } } } return;}
然后附上AC代码：
#include#include #include #include #include #include using namespace std;typedef long long lol;bool isprime[10000001];int prime[5000001],primesize,phi[10000001],n;lol ans;void find_prime(int listsize){ int i,j; memset(isprime,1,sizeof(isprime)); isprime[1]=false; phi[1]=1; for(i=2;i<=listsize;i++) { if(isprime[i]) { prime[++primesize]=i; phi[i]=i-1; } for(j=1;j<=primesize&&i*prime[j]<=listsize;j++) { isprime[i*prime[j]]=false; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else { phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } return;}int main(){ int i,j; scanf("%d",&n); find_prime(n); for(i=1;i<=primesize;i++) { int to=n/prime[i]; for(j=1;j<=to;j++) ans+=phi[j]*2; ans--; } printf("%lld\n",ans); return 0;}