1. 题目背景与核心需求解析

这道来自洛谷P1865的"A % B Problem"是GESP C++五级认证的典型练习题，考察的核心是数论中的质数判断与算法优化技巧。题目要求我们处理n次查询，每次给出区间[l,r]，需要统计该区间内质数的数量。看似简单的需求背后隐藏着几个关键挑战：

• 数据规模极大：m可达10^6，n最多1000次查询
• 时间效率要求高：朴素算法必然超时
• 边界条件复杂：需要处理查询越界情况

提示：在实际编程竞赛中，这类区间统计问题非常常见，但往往需要巧妙运用预处理和数学优化才能高效解决。

2. 算法选型与优化思路

2.1 朴素算法的局限性分析

最直观的做法是对每个查询区间[l,r]内的每个数进行质数判断。使用试除法判断质数的时间复杂度是O(√x)，对于最大10^6的区间，单次查询就需要约10^6×10^3=10^9次操作，显然无法在合理时间内完成。

// 低效的朴素解法示例（仅作反面教材） bool isPrime(int x) { if(x < 2) return false; for(int i=2; i*i<=x; ++i) if(x%i == 0) return false; return true; }

2.2 线性筛（欧拉筛）算法详解

线性筛法可以在O(m)时间内预处理出1~m的所有质数，其核心思想是让每个合数只被它的最小质因子筛除。我们使用一个标记数组prime_ary[]，其中prime_ary[i]=1表示i是质数。

算法流程：

1. 初始化标记数组，假设所有数都是质数
2. 从2开始遍历，遇到质数就加入质数列表
3. 用当前数与已知质数的乘积标记合数
4. 关键优化：当i能被当前质数整除时立即终止内层循环

int prime_ary[1000005]; // 标记数组 vector<int> primes; // 质数容器 void linearSieve(int m) { fill(prime_ary+2, prime_ary+m+1, 1); for(int i=2; i<=m; ++i) { if(prime_ary[i]) primes.push_back(i); for(int p : primes) { if(p*i > m) break; prime_ary[p*i] = 0; if(i%p == 0) break; // 关键优化点 } } }

2.3 前缀和优化查询效率

即使有了质数标记数组，每次查询仍需要遍历区间统计质数个数，最坏情况下仍是O(m)时间复杂度。这时可以引入前缀和数组prime_pre[]，其中prime_pre[i]表示[1,i]区间内质数的总数。

前缀和数组的构建：

prime_pre[0] = 0; for(int i=1; i<=m; ++i) prime_pre[i] = prime_pre[i-1] + prime_ary[i];

查询优化原理： 对于查询[l,r]，质数数量 = prime_pre[r] - prime_pre[l-1] 这使得单次查询时间复杂度降至O(1)

3. 完整实现与代码解析

3.1 输入输出处理

题目输入格式要求：

• 第一行：n(查询次数)和m(最大右端点)
• 接下来n行：每行l和r表示查询区间

输出要求：

• 区间合法时输出质数数量
• 区间越界时输出"Crossing the line"

3.2 边界条件处理

需要特别检查两种情况：

1. r > m
2. l < 1

这两种情况都视为查询越界，需要输出特定提示。

3.3 完整代码实现

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAX_M = 1e6+5; int prime_ary[MAX_M]; // 质数标记数组 int prime_pre[MAX_M]; // 前缀和数组 vector<int> primes; // 质数容器 void init(int m) { fill(prime_ary+2, prime_ary+m+1, 1); for(int i=2; i<=m; ++i) { if(prime_ary[i]) primes.push_back(i); for(int p : primes) { if(p*i > m) break; prime_ary[p*i] = 0; if(i%p == 0) break; } } for(int i=1; i<=m; ++i) prime_pre[i] = prime_pre[i-1] + prime_ary[i]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; init(m); while(n--) { int l, r; cin >> l >> r; if(r>m || l<1) { cout << "Crossing the line\n"; continue; } cout << prime_pre[r] - prime_pre[l-1] << "\n"; } return 0; }

4. 算法复杂度分析

• 预处理阶段：
  • 线性筛：O(m)
  • 前缀和计算：O(m)
• 查询阶段：
  • 每次查询：O(1)
  • n次查询：O(n)

总时间复杂度：O(m + n)，完全满足题目要求。

5. 常见问题与调试技巧

5.1 内存分配问题

当m=1e6时，数组大小需要略大于1e6以避免越界。建议：

const int MAX_M = 1e6+5; // 多分配一些空间

5.2 输入输出优化

对于大规模数据，建议关闭同步流加速IO：

ios::sync_with_stdio(false); cin.tie(nullptr);

5.3 特殊边界测试用例

测试时应特别注意以下情况：

1. l=1的查询
2. r=m的查询
3. 包含2的区间（最小的质数）
4. 大范围查询如[1,1e6]
5. 非法查询如[0,10]或[5,1e6+1]

5.4 欧拉筛常见错误

新手容易犯的错误：

1. 忘记初始化标记数组
2. 内层循环缺少break条件
3. 质数判断错误地将1视为质数
4. 数组大小设置不足导致越界

6. 算法扩展与变种思考

6.1 支持更大范围的查询

如果m扩大到1e8甚至更大，可以考虑：

1. 分段筛法
2. 使用bitset压缩存储空间
3. 多线程并行处理

6.2 统计其他数论函数

类似思路可用于统计：

1. 区间内素数幂次的数量
2. 区间内特定形式的素数（如孪生素数）
3. 区间内数的最大/最小质因子

6.3 在线算法优化

如果查询区间可能超出预处理范围，可以考虑：

1. Miller-Rabin素性测试（概率性算法）
2. 预先计算质数密度近似值

在实际编程竞赛训练中，我发现这类数论问题最关键的突破点往往在于识别出问题可以转化为前缀和差分的形式。预处理的思想在算法竞赛中极为常见，掌握好线性筛这类基础算法能为解决更复杂的问题打下坚实基础。