传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2818
若gcd(x, y) = 1，则gcd(x * n, y * n) = n。那么，当y固定不变时，小于y且与y互质的个数为phi(y)，所以此时对答案的贡献是phi(y) * 小于等于 n / y的素数的个数 * 2，最后乘2是因为数对是有序的。到最后，还要加上小于等于n的素数个数，因为(p, p)这种x = y的数对并没有计算进去。
#include <cstdio>
const int maxn = 10000005;
int n, prime[700000], tot, phi[maxn], mx, now;
char book[maxn];
long long ans;
int main(void) {
scanf("%d", &n);
for (int i = 2; i <= n; ++i) {
if (!book[i]) {
prime[++tot] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= tot; ++j) {
if (i * prime[j] > n) {
break;
}
book[i * prime[j]] = 1;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else {
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
int lmt = n >> 1;
now = tot;
for (int i = 2; i <= lmt; ++i) {
mx = n / i;
while (mx < prime[now]) {
--now;
}
ans += phi[i] * now;
}
printf("%lld\n", (ans << 1) + tot);
return 0;
}
原文：http://www.cnblogs.com/ciao-sora/p/6368531.html