题目链接：Link
### 题意
给定整数N，求 $1<=x,y<=N$ 且 $Gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对. (这个就是题面233333)
### 题解
~~很水的一道数论题~~
因为一个有序数对 $(x,y)$ 的 $GCD$ 若要是一个质数，那么必然的，$x, y$ 中必有一个是质数，否则不存在 $GCD$ 是质数的可能（自行思考，很简单）。
那么对于每一个质数 $p$ ，它的答案贡献就是 $(1$ ~ $\frac{n}{p}) $
对 $y$ 的取值范围进行讨论，当 $y = x $ 时， 有且仅有 $ y = x = 1$ 时 $x | y$
? 当 $y > x$ 时， 答案显然为$\varphi (y)$
最后的答案为所以有序互质对的个数为 $(1$ ~ $\frac{n}{p}) $ 的欧拉函数之和乘2减1（要求的是有序互质对，因为有正反所以乘2以后减去（1， 1）多算的一次）
### Code
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 6 const int SIZE = 1e7 + 5; 7 8 int n, p, tot; 9 int phi[SIZE], prime[SIZE], vis[SIZE]; 10 LL ans, sum[SIZE]; 11 12 inline void Euler() 13 { 14 phi[1] = 1; 15 for (int i = 2; i <= n; i++) 16 { 17 if (!vis[i]) { phi[i] = i - 1; prime[++tot] = i; } 18 for (int j = 1; j <= tot; j++) 19 { 20 int x = prime[j]; 21 if (i * x > n) break; 22 vis[i * x] = 1; 23 if (i % x == 0) { phi[i * x] = phi[i] * x; break; } 24 else phi[i * x] = phi[i] * phi[x]; 25 } 26 } 27 } 28 29 int main() 30 { 31 scanf("%d", &n); 32 Euler(); 33 for (int i = 1; i <= n; i++) 34 sum[i] = sum[i - 1] + phi[i]; 35 for (int i = 1; i <= tot; i++) 36 ans += sum[n / prime[i]] * 2 - 1; 37 printf("%lld", ans); 38 return 0; 39 }
原文：https://www.cnblogs.com/Tony102/p/11218834.html