素数最大公约数对

题目描述

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

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

输入格式

输入一个整数 $N$。

输出格式

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

数据范围

$1 \le N \le 10^7$

输入样例

4

输出样例

4

样例解释

对于 $N = 4$，满足条件的数对 $(x,y)$ 有：

1. $(2, 2)$：$\text{GCD}(2,2) = 2$（素数）
2. $(2, 4)$：$\text{GCD}(2,4) = 2$（素数）
3. $(3, 3)$：$\text{GCD}(3,3) = 3$（素数）
4. $(4, 2)$：$\text{GCD}(4,2) = 2$（素数）

注意：

• $(1, 1)$ 不满足，因为 $\text{GCD}(1,1) = 1$ 不是素数
• $(1, 2)$ 不满足，因为 $\text{GCD}(1,2) = 1$ 不是素数
• $(1, 3)$ 不满足，因为 $\text{GCD}(1,3) = 1$ 不是素数
• $(1, 4)$ 不满足，因为 $\text{GCD}(1,4) = 1$ 不是素数
• $(2, 3)$ 不满足，因为 $\text{GCD}(2,3) = 1$ 不是素数
• $(3, 4)$ 不满足，因为 $\text{GCD}(3,4) = 1$ 不是素数
• $(4, 4)$ 不满足，因为 $\text{GCD}(4,4) = 4$ 不是素数

所以总共有 4 对，输出 4。

问题分析

我们需要统计有多少对 $(x,y)$ 满足 $1 \le x, y \le N$ 且 $\text{GCD}(x,y)$ 是素数。

关键转化

设 $d = \text{GCD}(x,y)$，且 $d$ 是素数 $p$。

那么 $x = p \cdot x'$，$y = p \cdot y'$，其中 $\text{GCD}(x', y') = 1$。

约束条件：

1. $1 \le x \le N$ ⇒ $1 \le p \cdot x' \le N$ ⇒ $1 \le x' \le \lfloor N/p \rfloor$
2. $1 \le y \le N$ ⇒ $1 \le p \cdot y' \le N$ ⇒ $1 \le y' \le \lfloor N/p \rfloor$
3. $\text{GCD}(x', y') = 1$

数学形式

对于每个素数 $p \le N$，我们需要计算：

$$\sum_{x'=1}^{\lfloor N/p \rfloor} \sum_{y'=1}^{\lfloor N/p \rfloor} [\text{GCD}(x', y') = 1]$$

其中 $[\cdot]$ 是艾弗森括号，条件成立时值为1，否则为0。

欧拉函数关系

我们知道：

$$\sum_{i=1}^{n} \sum_{j=1}^{n} [\text{GCD}(i,j) = 1] = 2 \cdot \sum_{i=1}^{n} \varphi(i) - 1$$

其中 $\varphi(i)$ 是欧拉函数，表示 $1 \le k \le i$ 中与 $i$ 互质的数的个数。

推导：

• 当 $i = j$ 时：$[\text{GCD}(i,i)=1] = 1$ 当且仅当 $i=1$，所以这部分贡献为 1
• 当 $i \ne j$ 时：对于每个 $i$，与 $i$ 互质的 $j$ 有 $\varphi(i)$ 个，对称计算两次

因此：

$$\text{总数} = \sum_{i=1}^{n} \varphi(i) \times 2 - 1 = 2 \cdot \sum_{i=1}^{n} \varphi(i) - 1$$

最终公式

设 $S(n) = 2 \cdot \sum_{i=1}^{n} \varphi(i) - 1$，则答案为：

$$\text{答案} = \sum_{\text{素数 } p \le N} S\left(\left\lfloor \frac{N}{p} \right\rfloor\right)$$

算法步骤

1. 筛法求素数：使用线性筛或埃氏筛求出所有 $\le N$ 的素数
2. 计算欧拉函数前缀和：使用线性筛计算 $\varphi(i)$ 并求前缀和
3. 计算答案：对于每个素数 $p \le N$，累加 $S(\lfloor N/p \rfloor)$

时间复杂度

• 筛法：$O(N)$
• 计算答案：$O(\pi(N))$，其中 $\pi(N)$ 是 $\le N$ 的素数个数，约为 $N/\ln N$

总时间复杂度 $O(N)$，可以处理 $N \le 10^7$。

示例计算（N=4）

1. 素数 $\le 4$：$2, 3$

2. 计算欧拉函数：

   • $\varphi(1) = 1$
   • $\varphi(2) = 1$
   • $\varphi(3) = 2$
   • $\varphi(4) = 2$
   • 前缀和：$1, 2, 4, 6$

3. 对于 $p=2$：$\lfloor 4/2 \rfloor = 2$

   • $S(2) = 2 \times (1+1) - 1 = 2 \times 2 - 1 = 3$

4. 对于 $p=3$：$\lfloor 4/3 \rfloor = 1$

   • $S(1) = 2 \times 1 - 1 = 1$

5. 总答案：$3 + 1 = 4$

注意事项

1. 结果可能很大，需要使用 long long 类型
2. 线性筛可以同时求出素数和欧拉函数
3. 前缀和可以避免重复计算

时空限制

• 时间限制：1秒
• 空间限制：64MB