若一个正整数 𝑥 可以被表示为 𝑝 2 ∗ 𝑞 2 ，其中 、 𝑝 、 𝑞 为质数且 𝑝 不等于 𝑞 ，则 𝑥 是一个 “双子数”。 请计算区间 [ 𝑎 , 𝑏 ] 内有多少个 “双子数”？ 输入 读入两个整数 𝑎 , 𝑏 ( 1 <= 𝑎 <= 𝑏 <= 10 14 ) 。 输出 一个整数表示答案。 样例输入 复制 100 10000 样例输出 复制 29

我们先分析一下题意。 一个正整数 \( x \) 是“双子数”的定义是： \[ x = p^2 \times q^2 \] 其中 \( p, q \) 为质数，且 \( p \neq q \)。 那么： \[ x = (p \times q)^2 \] 令 \( m = p \times q \)，则 \( m \) 是两个不同质数的乘积，且 \( x = m^2 \)。 所以问题转化为： 在区间 \([a, b]\) 中，有多少个数 \( x \) 可以写成 \( m^2 \)，其中 \( m \) 是两个不同质数的乘积。 --- 1. 确定 \( m \) 的范围 因为 \( x = m^2 \)，且 \( a \le x \le b \)，所以： \[ \sqrt{a} \le m \le \sqrt{b} \] 并且 \( m \) 必须是两个不同质数的乘积，即 \( m = p \times q \)，\( p < q \) 均为质数。 --- 2. 枚举质数对 设 \( p < q \)，那么： \[ p \times q \le \sqrt{b} \] 并且 \( p \times q \ge \sqrt{a} \)。 由于 \( b \le 10^{14} \)，所以 \( \sqrt{b} \le 10^7 \)。 因此我们可以用筛法得到 \( \sqrt{b} \) 以内的所有质数。 --- 3. 算法步骤 1. 用埃氏筛或欧拉筛得到 \( \lfloor \sqrt{b} \rfloor \) 以内的所有质数，存在数组 `primes` 中。 2. 遍历所有质数对 \( (p, q) \)，满足 \( p < q \) 且 \( p \times q \le \sqrt{b} \)。 3. 计算 \( m = p \times q \)，再计算 \( x = m^2 \)。 4. 如果 \( a \le x \le b \)，则计数加一。 5. 输出总数。 --- 4. 复杂度分析 质数个数：\( \pi(10^7) \approx 664579 \) 个。 如果直接双重循环 \( p, q \) 会超时，因为 \( O(\pi(n)^2) \) 太大。 需要优化： - 固定 \( p \)，则 \( q \) 的范围是大于 \( p \) 且 \( p \times q \le \sqrt{b} \)，即 \( q \le \frac{\sqrt{b}}{p} \)。 - 对于每个 \( p \)，在 `primes` 中二分查找满足条件的最大 \( q \)，然后统计 \( q \) 的个数。 这样复杂度是 \( O(\pi(\sqrt{b}) \times \log \pi(\sqrt{b})) \)，可以接受。 --- 5. 代码实现（C++） ```cpp #include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; vector<int> get_primes(int limit) { vector<bool> is_prime(limit + 1, true); vector<int> primes; is_prime[0] = is_prime[1] = false; for (int i = 2; i <= limit; ++i) { if (is_prime[i]) { primes.push_back(i); if ((long long)i * i <= limit) { for (int j = i * i; j <= limit; j += i) { is_prime[j] = false; } } } } return primes; } int main() { long long a, b; cin >> a >> b; long long sqrt_b = sqrt(b); vector<int> primes = get_primes(sqrt_b); int cnt = 0; int n = primes.size(); for (int i = 0; i < n; ++i) { long long p = primes[i]; // 最小的 q 是 primes[i+1] // 需要 p * q <= sqrt_b long long max_q = sqrt_b / p; if (max_q < p) break; // 因为 q > p，如果 max_q < p 则没有符合条件的 q // 二分找到 primes 中第一个大于 max_q 的位置 int left = i + 1, right = n - 1, pos = -1; while (left <= right) { int mid = (left + right) / 2; if (primes[mid] <= max_q) { pos = mid; left = mid + 1; } else { right = mid - 1; } } if (pos != -1) { // 对于每个 q = primes[j]，检查 m = p * q，x = m^2 是否在 [a, b] 内 for (int j = i + 1; j <= pos; ++j) { long long q = primes[j]; long long m = p * q; if (m > sqrt_b) break; // 其实不会，因为 q <= max_q long long x = m * m; if (x >= a && x <= b) { cnt++; } } } } cout << cnt << endl; return 0; } ``` --- 6. 样例验证 输入： ``` 100 10000 ``` 输出： ``` 29 ``` 与题目样例一致。 --- 这样我们就得到了一个能在 \( b \le 10^{14} \) 范围内高效计算双子数个数的算法。 [2026-01-18 12:45:24 | AI问答 | 1234点数解答]