E. Interesting Ratio 详细题解

一、问题重述

定义函数：

$$F(a,b) = \frac{\operatorname{lcm}(a,b)}{\gcd(a,b)} $$

称 $F(a,b)$ 是“有趣的”，如果 $a < b$ 且 $F(a,b)$ 是质数。

给定 $n$，求满足 $1 \le a < b \le n$ 且 $F(a,b)$ 为质数的有序对 $(a,b)$ 的数量。

---

二、核心推导

2.1 化简 $F(a,b)$

设 $d = \gcd(a,b)$，则存在互质的正整数 $x, y$ 使得：

$$a = d \cdot x,\quad b = d \cdot y,\quad \gcd(x,y)=1 $$

此时：

$$\operatorname{lcm}(a,b) = d \cdot x \cdot y$$

因此：

$$F(a,b) = \frac{d \cdot x \cdot y}{d} = x \cdot y$$

2.2 质数条件

$F(a,b) = x \cdot y$ 为质数，且 $x, y$ 为正整数、互质。

由于质数只有两个正因子 $1$ 和自身，且 $x \cdot y$ 是质数，则必有一个为 $1$，另一个为质数。又因为 $a < b \implies d \cdot x < d \cdot y \implies x < y$，所以：

$$x = 1,\quad y = p\ \text{(质数)}$$

于是：

$$a = d \cdot 1 = d,\quad b = d \cdot p$$

且 $\gcd(d, d \cdot p) = d$ 自动成立，因为 $d$ 与 $p$ 互质。

2.3 问题转化

条件等价于：

• 选择一个质数 $p$
• 选择一个正整数 $d$，使得 $b = d \cdot p \le n$

即 $d \le \left\lfloor \frac{n}{p} \right\rfloor$。

对于每个固定的质数 $p$，$d$ 可以取 $1, 2, \dots, \lfloor n/p \rfloor$，共 $\lfloor n/p \rfloor$ 个取值。

2.4 最终答案

对所有不超过 $n$ 的质数 $p$ 求和：

$$\text{ans}(n) = \sum_{p \le n,\ p\ \text{prime}} \left\lfloor \frac{n}{p} \right\rfloor $$

---

三、算法实现

1. 用埃氏筛预处理 $[1, 10^7]$ 内的质数表
2. 对每个测试用例，遍历所有 $\le n$ 的质数，累加 $\lfloor n/p \rfloor$
3. 时间复杂度：$O(\pi(n))$ 每个用例，总 $\sum n \le 10^7$，可接受

---

四、标程代码

#include <iostream>
using namespace std;

const int MAXN = 10000001;
bool prime[MAXN];

void solve() {
    int n;
    cin >> n;
    long long ans = 0;  // 注意答案可能超过 int 范围
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            ans += n / i;
        }
    }
    cout << ans << endl;
}

int main() {
    // 初始化质数标记
    for (int i = 0; i < MAXN; i++) prime[i] = true;
    prime[0] = prime[1] = false;
    
    // 埃氏筛
    for (int i = 2; i * i < MAXN; i++) {
        if (!prime[i]) continue;
        for (int j = i * i; j < MAXN; j += i) {
            prime[j] = false;
        }
    }
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

五、示例验证

示例 1：$n = 5$

质数 $\le 5$：$2, 3, 5$

• $p=2$：$\lfloor 5/2 \rfloor = 2$ → $(d=1,2)$ → $(1,2),(2,4)$
• $p=3$：$\lfloor 5/3 \rfloor = 1$ → $(d=1)$ → $(1,3)$
• $p=5$：$\lfloor 5/5 \rfloor = 1$ → $(d=1)$ → $(1,5)$ 总数 $2+1+1=4$ ✅

示例 2：$n = 10$

质数：$2,3,5,7$

• $2$：$\lfloor 10/2 \rfloor = 5$
• $3$：$\lfloor 10/3 \rfloor = 3$
• $5$：$\lfloor 10/5 \rfloor = 2$
• $7$：$\lfloor 10/7 \rfloor = 1$ 总和 $5+3+2+1=11$ ✅

示例 3：$n = 34$

质数 $p \le 34$ 求和：计算得 $49$ ✅

---

六、复杂度分析

• 预处理：$O(MAXN \log \log MAXN)$
• 每个测试用例：$O(\pi(n)) \approx O(n / \log n)$
• 总 $\sum n \le 10^7$，完全可行

---

七、总结

步骤	操作
1	设 $d = \gcd(a,b)$，$a = d \cdot x$，$b = d \cdot y$
2	$F(a,b) = x \cdot y$ 为质数 ⇒ $x=1$，$y=p$ 为质数
3	$a = d$，$b = d \cdot p$，约束 $d \cdot p \le n$
4	对每个质数 $p$，$d$ 可取 $1$ 到 $\lfloor n/p \rfloor$
5	答案 = $\sum_{p\le n} \lfloor n/p \rfloor$

核心公式：

$$\boxed{\text{ans}(n) = \sum_{p\ \text{prime} \le n} \left\lfloor \frac{n}{p} \right\rfloor} $$