【GESP】C++五级练习题 luogu-P1865 A % B Problem
GESP C++ 五级练习题，数论和前缀和思想考点，四级考生也可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。
luogu-P1865 A % B Problem
题目要求
题目背景
题目名称是吸引你点进来的。 实际上该题还是很水的。
题目描述
给定 $l, r$，求区间 $[l, r]$ 内质数的个数。
输入格式
第一行有两个整数，分别代表询问次数 $n$ 和 给定区间的右端点最大值 $m$。
接下来 $n$ 行，每行两个整数 $l, r$，代表一次查询。
输出格式
对于每次查询输出一行，若 $l, r \in [1, m]$，则输出区间质数个数，否则输出
Crossing the line。
输入输出样例 #1
输入 #1
1
2
3
2 5
1 3
2 6
输出 #1
1
2
2
Crossing the line
说明/提示
数据范围与约定
- 对于 $20\%$ 的数据，保证 $n,m\le 10$。
- 对于 $100\%$ 的数据，保证 $1\le n\le1000$，$1\le m\le10^6$，$-10^9\le l\le r\le 10^9$。
题目分析
这道题目要求我们在 $n$ 次询问中，计算给定区间 $[l, r]$ 内质数的个数。
1. 朴素算法的局限性
如果对于每一次询问 $[l, r]$，我们都遍历区间内的每一个数并判断其是否为质数，时间复杂度会非常高。
- 单次判断质数（试除法）的复杂度约为 $O(\sqrt{x})$。
- 区间长度最大可达 $10^6$。
- 总共有 $n$ 次询问。 这样总的时间复杂度在最坏情况下会达到 $O(n \cdot m \sqrt{m})$，对于 $m=10^6, n=1000$ 的数据规模，计算量约为 $10^9$，肯定会超时（TLE）。
2. 预处理：线性筛（欧拉筛）
由于所有询问的区间右端点都在 $m$ 以内（$m \le 10^6$），我们可以预先找出 $1$ 到 $m$ 之间的所有质数。 这里推荐使用 线性筛（欧拉筛） 算法，它可以在 $O(m)$ 的线性时间内筛选出 $1 \sim m$ 之间的所有质数。
- 我们维护一个标记数组
prime_ary，prime_ary[i] = 1表示 $i$ 是质数。 - 通过“用最小质因子筛去合数”的策略，确保每个合数只被标记一次，从而达到线性复杂度。
3. 查询优化：前缀和
虽然我们已经快速判断了每个数是否为质数，但如果每次查询仍需遍历 $[l, r]$ 来统计个数，单次查询复杂度为 $O(r-l)$，最坏情况仍需 $O(n \cdot m)$，依然可能超时。 为了在 $O(1)$ 的时间内回答询问，我们需要结合前缀和思想：
- 定义数组
prime_pre[i]表示区间 $[1, i]$ 中质数的总个数。 - 递推公式：
prime_pre[i] = prime_pre[i-1] + (i 是质数 ? 1 : 0)。 - 对于任意查询 $[l, r]$，其质数个数等于 $[1, r]$ 的质数个数减去 $[1, l-1]$ 的质数个数，即
prime_pre[r] - prime_pre[l-1]。
4. 边界处理
题目要求如果查询区间 $[l, r]$ 超出了 $[1, m]$ 的范围，输出 “Crossing the line”。因此在处理询问前，需要先判断 r > m 或 l < 1。
总结
算法流程如下：
- 读取 $n$ 和 $m$。
- 使用线性筛预处理出 $1 \sim m$ 的质数标记数组。
- 计算质数标记数组的前缀和。
- 依次处理 $n$ 次询问，利用前缀和 $O(1)$ 输出答案或判断越界。
总时间复杂度为 $O(m + n)$，完全符合要求。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
// 标记数组：prime_ary[i] 为 1 表示 i 是质数，为 0 表示 i 是合数
int prime_ary[1000005];
// 前缀和数组：prime_pre[i] 表示 [1, i] 区间内质数的个数
int prime_pre[1000005];
int main() {
int n, m;
// 输入询问次数 n 和最大范围 m
std::cin >> n >> m;
std::vector<int> primes; // 用于存储筛选出的质数
// 初始化：假设 2 到 m 之间的数都是质数
std::fill(prime_ary + 2, prime_ary + m + 1, 1);
// 线性筛（欧拉筛）算法筛选质数
for (int i = 2; i <= m; i++) {
if (prime_ary[i] == 1) {
primes.push_back(i); // i 是质数，加入列表
}
// 遍历已有质数，标记合数
for (int p : primes) {
if (p * i > m) {
break; // 如果超出最大范围 m，停止这一轮标记
}
prime_ary[p * i] = 0; // 标记 p * i 为合数
if (i % p == 0) {
break; // 关键：保证每个合数只被其最小质因子筛去，保证线性时间复杂度
}
}
}
// 计算质数个数的前缀和
for (int i = 1; i <= m; i++) {
prime_pre[i] = prime_pre[i - 1] + prime_ary[i];
}
// 处理 n 次询问
for (int i = 0; i < n; i++) {
int l, r;
std::cin >> l >> r;
// 判断查询区间是否超出有效范围 [1, m]
if (r > m || l < 1) {
std::cout << "Crossing the line" << "\n";
continue;
}
// 利用前缀和计算区间 [l, r] 内的质数个数
std::cout << prime_pre[r] - prime_pre[l - 1] << "\n";
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
