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

2 5
1 3
2 6

输出 #1

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)$ ，完全符合要求。

示例代码

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2025年12月28日

luogu-P1413 坚果保龄球 luogu-P1160 队列安排