问题：求gcd(x,y)==质数, 1<=x,y<=n的有多少对？
(x, y) = 1, 1 <= x, y <= n/k(x, y) = 1, 1 <= x, y <= n/p的个数。
(x, y) = 1 的个数如何求呢？欧拉函数！
#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#include <math.h>#include <ctype.h>#include <time.h>#include <queue>#include <iterator>using namespace std;const int MAXN = 1000000;int n;int main(){while (scanf("%d", &n) != EOF){bool com[MAXN];int primes = 0, prime[MAXN], phi[MAXN];phi[1] = 1;for (int i = 2; i <= n; ++i){if (!com[i]){prime[primes++] = i;phi[i] = i – 1;}for (int j = 0; j < primes && i*prime[j] <= n; ++j){com[i*prime[j]] = true;if (i % prime[j])phi[i*prime[j]] = phi[i] * (prime[j] – 1);else{phi[i*prime[j]] = phi[i] * prime[j]; break;}}}for (int i = 2; i <= n; i++)phi[i] = phi[i] + phi[i-1];long long ans = 0;for (int i = 0; i < primes; i++)ans += phi[n/prime[i]] * 2 -1;printf("%lld\n",ans);}return 0;}
，旅行，不要害怕错过什么，
