最大公约数

给定整数 $N$，求 $1 \leq x,y \leq N$ 且 $\text{GCD}(x,y)$ 为素数的数对 $(x,y)$ 有多少对。

$\text{GCD}(x,y)$ 即求 $x$，$y$ 的最大公约数。

输入格式

输入一个整数 $N$。

输出格式

输出一个整数，表示满足条件的数对数量。

数据范围

$1 \leq N \leq {10}^{7}$

输入样例：

4

输出样例：

4

解题思路

　　直接枚举$(x, y)$是不可取的，如果定义一种映射关系$(x, y) \stackrel{f}{\longrightarrow} p$，其中$p$是质数。因此当数对$(x, y)$的最大公约数为质数就满足这个映射关系。可以发现自变量很多，而因变量很少，因此考虑能不能来枚举因变量来求自变量的个数。

　　枚举$1 \sim N$种的每一个质数$p$，如果有$\gcd(x, y) = p$，那么有$\gcd(\frac{x}{p}, \frac{y}{p}) = 1$。记$x' = \frac{x}{p}$，$y' = \frac{y}{p}$，满足$1 \leq x', y' \leq \left\lfloor {\frac{N}{p}} \right\rfloor$。因此问题从在$1 \sim N$中有多少个$(x, y)$的$\gcd(x, y) = p$变成了在$1 \sim \left\lfloor {\frac{N}{p}} \right\rfloor$中有多少个$(x, y)$的$\gcd(x, y) = 1$，就是可见的点的模型。

　　因此对于质数$p$，所要求的$(x, y)$的个数为$s_p = 2 \cdot \sum\limits_{i = 2}^{\left\lfloor {\frac{N}{p}} \right\rfloor}{\varphi(i)} + 1$。因此总的答案就是$\sum\limits_{\text{不超过N的质数}p}{s_p}$。因此还需要对$\varphi(i)$求一个前缀和。

　　AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 
 6 const int N = 1e7 + 10;
 7 
 8 int primes[N], cnt;
 9 bool vis[N];
10 int phi[N];
11 LL s[N];
12 
13 void get_prime(int n) {
14     // phi[1] = 1    // 这题中定义phi(1)=0
15     for (int i = 2; i <= n; i++) {
16         if (!vis[i]) primes[cnt++] = i, phi[i] = i - 1;
17         for (int j = 0; primes[j] <= n / i; j++) {
18             vis[primes[j] * i] = true;
19             if (i % primes[j] == 0) {
20                 phi[primes[j] * i] = phi[i] * primes[j];
21                 break;
22             }
23             phi[primes[j] * i] = phi[i] * (primes[j] - 1);
24         }
25     }
26 }
27 
28 int main() {
29     int n;
30     cin >> n;
31     get_prime(n);
32     for (int i = 1; i <= n; i++) {  // 对phi[i]求前缀和
33         s[i] = s[i - 1] + phi[i];
34     }
35     LL ret = 0;
36     for (int i = 0; i < cnt; i++) {
37         ret += 2 * s[n / primes[i]] + 1;
38     }
39     cout << ret;
40     
41     return 0;
42 }

参考资料

　　AcWing 220. 最大公约数（算法提高课）：https://www.acwing.com/video/695/