信息学奥赛算法练功房◌检测中
题单　·　习题解析

洛谷 P1865 A % B Problem

★ 筛 + 前缀和（[第 6 章](/ch/06-prefix-diff/)那把尺子原样再用一次），每询问 O(1)；⚠⚠ 而**草稿又被实测打回来**：「每询问重扫一遍 = 10⁹ 次必然 TLE」是错的 —— 顶格最坏本机 **0.24 秒 / 时限 1 秒，它能 AC**（内层顺序扫 1 MB 的表，-O2 向量化了）⇒ [复杂度不等于耗时](/sol/p1372/)第二次；★ 正解赢的是 **180 倍** ＋「**它不依赖题面那句 n ≤ 1000**」；★★★ 真正咬人的是那句「若 l, r ∈ [1, m]」—— 数据范围里写着 **−10⁹ ≤ l**，⇒ **两头都要判**，而「只判 r > m」那个错法有一个结构性的盲区：触发要 **l < 1 且 r ≤ m 同时成立**，是**两个不同分量上的约束的交**（概率约 3×10⁻⁸）⇒ **顺手写的档和「照题面随机」档都是精确的 0**，只有照着那条线造才 300/300；⚠⚠ 外加一条自己踩的：第一版「照题面」档量出「被抓 243/300」，而那不是答错 —— r 为负时它去读 **cnt[−5×10⁸]**，**崩了**；⇒ **对拍把「崩了」和「答错了」记成同一件事**，而前者的数字是 UB 派生的、不可复现 ⇒ 那一档只能收窄

原题：洛谷 P1865出自 第 41 章 质数：试除 → 埃氏筛 → 线性筛 的题单题面本地存档：2026-09-02
⚠ 先自己写一遍，再往下看

这一页不是标准答案，是一条阶梯：把大多数人真实会写出的第一版摆出来， 看它错在哪、慢在哪，再一步一步改。所以它对「已经自己动手撞过一次墙」的人最有用。
还没写过的话，先去写 —— 写出来的哪怕是错的，也比直接看这一页收获大。

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。 所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1865，日期见页头。两边不一致时信原站。

题目背景

题目名称是吸引你点进来的。实际上该题还是很水的。

题目描述

给定 l、r，求区间 [l, r] 内质数的个数。

输入格式

第一行有两个整数，分别代表询问次数 n 和给定区间的右端点最大值 m。

接下来 n 行，每行两个整数 l、r，代表一次查询。

输出格式

对于每次查询输出一行，若 l, r ∈ [1, m]，则输出区间质数个数，否则输出 Crossing the line。

数据范围与约定

  • 对于 20% 的数据，保证 n, m ≤ 10。
  • 对于 100% 的数据，保证 1 ≤ n ≤ 1000，1 ≤ m ≤ 10⁶，−10⁹ ≤ l ≤ r ≤ 10⁹。

时限 1 秒，内存 125 MB（128000 KB）。

输入输出样例

输入

2 5
1 3
2 6

输出

2
Crossing the line

m = 5。第一问 [1, 3] 里有 2、3 两个质数；第二问 r = 6 > m = 5 ⇒ 越界。

1第 ① 版：每个询问从 l 数到 r，一个一个判质数

p1865Brute.cpp第 ① 版：每询问 × 每个数 × 试除 —— 参照物，而且它能拿 20 分
// 第 ① 版：每个询问从 l 数到 r，一个一个试除判质数 —— 参照物
//
// 顶格 n = 1000 个询问 × 区间长 10⁶ × 每个数试除 √x ⇒ 想都不用想。
// 但它是**唯一一条和「筛 + 前缀和」完全无关的路**，本页所有对拍拿它当标准答案。
#include <bits/stdc++.h>
using namespace std;


static bool isPrime(int x) {
    if (x < 2) return false;
    for (long long i = 2; i * i <= x; i++) if (x % i == 0) return false;
    return true;
}


int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int q = 0; q < n; q++) {
        int l, r;
        if (scanf("%d %d", &l, &r) != 2) break;
        if (l < 1 || r > m) { puts("Crossing the line"); continue; }
        int c = 0;
        for (int i = l; i <= r; i++) if (isPrime(i)) c++;
        printf("%d\n", c);
    }
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
★ 它不是零分 —— 题面第一行分档就是出题人递过来的工具
量的是 独占实测（3 次取中位数）
一个 [1, 10⁶] 的询问要多久 约 165 毫秒
顶格 1000 个这样的询问 ⇒ 外推 ★ 约 165 秒 / 时限 1 秒
而题面写着「对于 20% 的数据，n, m ≤ 10」 ★ 稳拿 20 分

⇒ 「暴力值多少分」是「暴力 × 那道题分档」的属性， 读数据范围的时候顺手把每一档乘一遍。

2第 ② 版：筛一次，然后每个询问在筛出来的表上扫一遍

p1865Scan.cpp★ 第 ② 版：筛 + 每询问重扫 —— 而它其实就已经能过了
// ⚠ 第 ② 版：筛一次是对的，可每个询问还是从 l 扫到 r 累加
//
// ★★ 它的答案永远是对的，而**它其实也能 AC** —— 这一句是我的草稿被实测打回来的。
//   草稿写的是「顶格 1000 × 10⁶ = 10⁹ 次，必然 TLE」。
//   实测：顶格**最坏**（1000 个询问全问 [1, m]）本机 **0.23 秒 / 时限 1 秒**。
//   道理不玄：内层是 `if (!comp[x]) c++`，一个字节一个字节**顺序**扫，-O2 把它向量化了
//   ⇒ [复杂度不等于耗时，循环体里有什么才算](/sol/p1372/)。
//
// ⇒ 所以正解赢的不是「能不能过」，是 **1 毫秒 vs 230 毫秒**，
//   以及**它不依赖题面那句 n ≤ 1000**（把 n 抬到 10⁵，这一版当场死透）。
#include <bits/stdc++.h>
using namespace std;


static const int MAXM = 1000000;
static bool comp[MAXM + 1];


int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (long long i = 2; i * i <= m; i++)
        if (!comp[i]) for (long long j = i * i; j <= m; j += i) comp[j] = true;


    for (int q = 0; q < n; q++) {
        int l, r;
        if (scanf("%d %d", &l, &r) != 2) break;
        if (l < 1 || r > m) { puts("Crossing the line"); continue; }
        int c = 0;
        for (int i = max(l, 2); i <= r; i++) if (!comp[i]) c++;   // 每次都重扫一遍
        printf("%d\n", c);
    }
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
⚠⚠ 我的草稿写的是「10⁹ 次，必然 TLE」—— 实测把它打回来了
顶格 n = 1000、m = 10⁶ 扫过的格子 本机耗时（独占实测，3 次取中位数）
顶格随机 340 750 971 0.08 秒
顶格最坏（1000 个询问全问 [1, m]） 1 000 000 000 ★ 0.24 秒 / 时限 1 秒
倍数 ★ 2.93 倍

⇒ 它能 AC。 道理不玄：内层是 if (!comp[x]) c++， 一个字节一个字节顺序扫过一张 1 MB 的表，-O2 把它向量化了 —— 复杂度不等于耗时，循环体里有什么才算（上一章 P1372 那条的第二次现场）。

★ 顺带又是一次「顶格 ≠ 最坏」：顶格随机只有最坏的 34%。 ⚠ 而这一次它无关生死 —— 两头都过得去，这也是这条规律该有的样子。

3★ 第 ③ 版：前缀和 —— 赢的不是「能不能过」

★ cnt[i] = 1..i 里有几个质数，区间一减就出来
cnt[i] = cnt[i-1] + (i 是质数 ? 1 : 0)
答案  = cnt[r] − cnt[l−1]

第 6 章那把尺子原样再用一次，每个询问 O(1)。

p1865.cpp★ 正解：埃氏筛 + 前缀和，每询问 O(1)
// P1865 A % B Problem —— 正解：埃氏筛一次 + 前缀和，每个询问 O(1)
//
// ★ 两把尺子都在第 6 章和第 41 章学过，这道题只是把它们摞在一起：
//   ① 筛出 [1, m] 里谁是质数（一次，O(m log log m)）；
//   ② cnt[i] = 1..i 里有几个质数（前缀和），区间一减就出来。
//
// ⚠⚠ 真正咬人的是那句「若 l, r ∈ [1, m]」—— **两头都要判**：
//   题面写着 −10⁹ ≤ l，所以 **l 可以是负数**，而绝大多数人只判了 r > m。
#include <bits/stdc++.h>
using namespace std;


static const int MAXM = 1000000;
static int cnt[MAXM + 1];
static bool comp[MAXM + 1];


int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (long long i = 2; i * i <= m; i++)
        if (!comp[i]) for (long long j = i * i; j <= m; j += i) comp[j] = true;
    for (int i = 1; i <= m; i++) cnt[i] = cnt[i - 1] + (i >= 2 && !comp[i] ? 1 : 0);


    for (int q = 0; q < n; q++) {
        int l, r;
        if (scanf("%d %d", &l, &r) != 2) break;
        if (l < 1 || r > m) puts("Crossing the line");
        else printf("%d\n", cnt[r] - cnt[l - 1]);
    }
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
★★ 它值多少：180 倍，外加一句「不依赖题面」
顶格最坏 本机耗时
第 ② 版（每询问重扫） 0.24 秒
★ 正解（前缀和） 1.3 毫秒
倍数 ★ 约 180 倍

⇒ 但更要紧的是第二行理由：第 ② 版能过，靠的是题面那句 n ≤ 1000。 把询问数抬到 10⁵（别的一个字不改），它当场死透，而正解一动不动。 ⇒ 「这个技巧在这道题上成立」和「这道题该用它」是两句话， 而这一页给出了第三句：它现在能过，是靠题面里的哪一个数？

4⚠⚠ 真正咬人的那一条：越界要判两头

★★★ 题面把它写在输出格式里，而所有人只看见了一半

若 l, r ∈ [1, m]，则输出区间质数个数，否则输出 Crossing the line。

而数据范围那一行写着 −10⁹ ≤ l ⇒ l 可以是负数、可以是 0。

⇒ 判据是 l < 1 || r > m，两头都要。 绝大多数人只写了 r > m（下面那个错法），而它有一个极其干净的盲区。

p1865NoLow.cpp✗ 错法一：越界只判了右边
p1865One.cpp✗ 错法二：把 1 也数成了质数
p1865Off.cpp✗ 错法三：cnt[r] − cnt[l]（少减了一格）
p1865Gen.cpp生成器（三档：顺手写的 / 照题面 / 照着那条线造）
★★★ 「照题面随机」这一次也不够 —— 而原因是新的
档位（每档 300 轮） 落在 [1, m] 内的询问 ✗ 只判右边 ✗ 1 当成质数 ✗ 少减一格
0 顺手写的（l, r 都在 [1, m] 里） 1673 / 1673 ★ 精确的 0 98 250
⚠⚠ 1 照题面随机（l 可以到 −10⁹） ★ 0 / 1673 ★ 精确的 0 0 0
2 照着 l < 1 那条线造 0 / 1673 ★ 300 / 300 0 0

★ 三个 bug 的「满足触发条件」和「真被抓」一个不差（98 ≡ 98、250 ≡ 250、300 ≡ 300）。

★★★ 而第 ② 行是这一节的主角：照题面随机也抓不到它，而且是结构性的 0。 触发条件是 l < 1 且 r ≤ m —— 这是两个不同分量上的约束的交： l 那一头题面给了 2 × 10⁹ 宽的值域，r 那一头却要落进 [1, m]（这里 m ≤ 60） ⇒ 概率是两者相乘，约 3 × 10⁻⁸。

⇒ ★★ 触发条件是两层的，而这一次两层长在输入的不同分量上 —— 这种交集只能照着那条线直接造，加多少轮、换多少种子都没用。

⚠ 而第 ② 行还顺带演了一次「一致有两种：都算对了，和都没算」的极端： 那 300 轮里 一个合法询问都没有 ⇒ 「筛 + 前缀和」那半个程序一次都没被执行过， 验的全是 Crossing the line 这一行字。

⚠⚠ 自己踩的：第一版的「照题面」档量出「被抓 243 / 300」，而那不是它答错

第一版的档 1 老老实实照题面让 l, r ∈ [−10⁹, 10⁹]，跑出来「只判右边」那版被抓 243 / 300。 差点就写进表里了 —— 可它不是答错：

r 是负数的时候，r > m 不成立 ⇒ 它接着去算 cnt[r]，也就是 cnt[−5×10⁸] —— 拿负下标读数组，越界。 那 243 轮里它是崩掉的，不是算错的。

⇒ ★★★ 对拍把「崩了」和「答错了」记成同一件事，而前者的数字是 UB 派生的、不可复现（换个编译器、换个数组布局就变）。 ⇒ 所以档 1 收窄成「r ≥ 1，l 照题面」——收窄的理由写在生成器注释里。 ★ 收窄之后那一档变成精确的 0，而那个 0 才是真的、能证的。

5★ 哪一版就已经能过了

p1865Count.cpp本页所有数字的出处
// P1865 的度量程序：./p1865Count csv        （本页的数字都出自它）
//
//   legal : ★★★ 三个档里「真的落在 [1, m] 内的询问」有几个 ——
//           **照题面随机那一档是 0**，也就是说那 300 轮验的全是「Crossing the line」
//           这一行字，素数计数那半个程序[一次都没被执行](/sol/p1746/)。
//   scan  : ★★ 「每询问重扫一遍」扫过多少格 —— 顶格随机 ↔ 顶格最坏（全问 [1, m]）。
//   ms    : 秒表：正解 ↔ 重扫版，两种顶格各量一次。
//   io    : ⚠ 一笔否定结论：这道题最多 1000 行询问，读入优化一点用都没有。
//
// ⚠ 这里**复刻**了 p1865Gen.cpp 的档位逻辑（同一个 mt19937、同一个种子公式）。
// ⚠ 秒表用 steady_clock 在进程内量，每档跑 3 次取中位数
//   （[第 12 章 P1923 那一跤](/sol/p1923/)：秒表断言的主语是余量，不是量级）。
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;


static const int MAXM = 1000000;
static int cntTab[MAXM + 1];
static bool comp[MAXM + 1];


static void sieve(int m) {
    memset(comp, 0, sizeof(bool) * (m + 1));
    for (long long i = 2; i * i <= m; i++)
        if (!comp[i]) for (long long j = i * i; j <= m; j += i) comp[j] = true;
    cntTab[0] = 0;
    for (int i = 1; i <= m; i++) cntTab[i] = cntTab[i - 1] + (i >= 2 && !comp[i] ? 1 : 0);
}


/** 复刻 p1865Gen.cpp 的档 0 / 1 / 2 */
static void genRound(unsigned seed, int mode, int& n, int& m, vector<pair<long long, long long>>& qs) {
    mt19937 rng(seed * 1000003u + 20260902u);
    m = 5 + (int)(rng() % 56u);
    n = 1 + (int)(rng() % 10u);
    qs.clear();
    for (int i = 0; i < n; i++) {
        long long l, r;
        if (mode == 0) {
            long long a = 1 + (long long)(rng() % (unsigned)m), b = 1 + (long long)(rng() % (unsigned)m);
            l = min(a, b); r = max(a, b);
        } else if (mode == 1) {
            r = 1 + (long long)(rng() % 1000000000u);
            l = (long long)(rng() % 2000000001u) - 1000000000LL;
            if (l > r) l = -(long long)(rng() % 1000000001u);
        } else {
            l = -(long long)(rng() % 101u);
            r = 1 + (long long)(rng() % (unsigned)m);
        }
        qs.push_back({l, r});
    }
}


static double median3(double a, double b, double c) { return max(min(a, b), min(max(a, b), c)); }


int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");


    /* ① 三个档里合法询问的个数 ＋ 三个 bug 的触发轮数 */
    long long legal[3] = {0, 0, 0}, total[3] = {0, 0, 0};
    int trigNoLow[3] = {0, 0, 0}, trigOne[3] = {0, 0, 0}, trigOff[3] = {0, 0, 0};
    for (int mode = 0; mode < 3; mode++) {
        for (int s = 1; s <= 300; s++) {
            int n, m; vector<pair<long long, long long>> qs;
            genRound((unsigned)s, mode, n, m, qs);
            bool hLow = false, hOne = false, hOff = false;
            for (auto& q : qs) {
                long long l = q.first, r = q.second;
                total[mode]++;
                if (l >= 1 && r <= m) {
                    legal[mode]++;
                    if (l == 1) hOne = true;
                    bool pr = l >= 2;
                    for (long long d = 2; d * d <= l && pr; d++) if (l % d == 0) pr = false;
                    if (pr) hOff = true;
                }
                if (l < 1 && r <= m) hLow = true;
            }
            trigNoLow[mode] += hLow; trigOne[mode] += hOne; trigOff[mode] += hOff;
        }
    }


    /* ② 顶格：随机 ↔ 最坏（全问 [1, m]），先数格子再上秒表 */
    const int N = 1000, M = 1000000;
    vector<pair<int, int>> rnd(N), worst(N);
    {
        mt19937 rng(20260902u);
        for (int i = 0; i < N; i++) {
            int a = 1 + (int)(rng() % (unsigned)M), b = 1 + (int)(rng() % (unsigned)M);
            if (a > b) swap(a, b);
            rnd[i] = {a, b};
            worst[i] = {1, M};
        }
    }
    long long cellsRnd = 0, cellsWorst = 0;
    for (int i = 0; i < N; i++) {
        cellsRnd += rnd[i].second - rnd[i].first + 1;
        cellsWorst += worst[i].second - worst[i].first + 1;
    }


    double msFast[3], msScanR[3], msScanW[3];
    for (int rep = 0; rep < 3; rep++) {
        {
            auto t0 = steady_clock::now();
            sieve(M);
            volatile long long acc = 0;
            for (int i = 0; i < N; i++) acc = acc + (cntTab[rnd[i].second] - cntTab[rnd[i].first - 1]);
            msFast[rep] = duration<double, milli>(steady_clock::now() - t0).count();
        }
        {
            auto t0 = steady_clock::now();
            sieve(M);
            volatile long long acc = 0;
            for (int i = 0; i < N; i++) {
                long long c = 0;
                for (int x = max(rnd[i].first, 2); x <= rnd[i].second; x++) if (!comp[x]) c++;
                acc = acc + c;
            }
            msScanR[rep] = duration<double, milli>(steady_clock::now() - t0).count();
        }
        {
            auto t0 = steady_clock::now();
            sieve(M);
            volatile long long acc = 0;
            for (int i = 0; i < N; i++) {
                long long c = 0;
                for (int x = max(worst[i].first, 2); x <= worst[i].second; x++) if (!comp[x]) c++;
                acc = acc + c;
            }
            msScanW[rep] = duration<double, milli>(steady_clock::now() - t0).count();
        }
    }
    double mf = median3(msFast[0], msFast[1], msFast[2]);
    double mr = median3(msScanR[0], msScanR[1], msScanR[2]);
    double mw = median3(msScanW[0], msScanW[1], msScanW[2]);


    /* ②b 第 ① 版（试除判质数）：量一个 [1, m] 的询问，再乘 1000 外推顶格 */
    double msBruteOne;
    {
        auto t0 = steady_clock::now();
        volatile long long c = 0;
        for (int x = 2; x <= M; x++) {
            bool pr = true;
            for (long long d = 2; d * d <= x; d++) if (x % d == 0) { pr = false; break; }
            if (pr) c = c + 1;
        }
        msBruteOne = duration<double, milli>(steady_clock::now() - t0).count();
    }


    /* ③ 读入量：顶格 1000 行，每行两个 ≤ 10⁹ 的数 */
    long long ioBytes = 0;
    { char buf[64]; for (int i = 0; i < N; i++) ioBytes += snprintf(buf, sizeof buf, "%d %d\n", rnd[i].first, rnd[i].second); }


    if (csv) {
        for (int m = 0; m < 3; m++) printf("legal%d,%lld\n", m, legal[m]);
        for (int m = 0; m < 3; m++) printf("total%d,%lld\n", m, total[m]);
        for (int m = 0; m < 3; m++) printf("trigLow%d,%d\n", m, trigNoLow[m]);
        for (int m = 0; m < 3; m++) printf("trigOne%d,%d\n", m, trigOne[m]);
        for (int m = 0; m < 3; m++) printf("trigOff%d,%d\n", m, trigOff[m]);
        printf("cellsRnd,%lld\n", cellsRnd);
        printf("cellsWorst,%lld\n", cellsWorst);
        printf("cellRatio,%.2f\n", (double)cellsWorst / (double)cellsRnd);
        printf("msFast,%.2f\n", mf);
        printf("msScanRnd,%.0f\n", mr);
        printf("msScanWorst,%.0f\n", mw);
        printf("scanOverFast,%.1f\n", mr / mf);
        printf("worstOverFast,%.1f\n", mw / mf);
        printf("msBruteOne,%.0f\n", msBruteOne);
        printf("projBruteSec,%.0f\n", msBruteOne * N / 1000.0);
        printf("ioBytes,%lld\n", ioBytes);
        return 0;
    }


    printf("① 三个档里「真的落在 [1, m] 内」的询问\n");
    const char* NAME[3] = {"顺手写的（l, r 都在 [1, m] 里）", "★ 照题面随机（l 可以到 −10⁹）", "照着 l < 1 那条线造"};
    for (int m = 0; m < 3; m++)
        printf("   档 %d %s：%lld / %lld 个合法；触发轮数 NoLow %d / One %d / Off %d\n",
               m, NAME[m], legal[m], total[m], trigNoLow[m], trigOne[m], trigOff[m]);
    printf("   ⇒ ★★★ 档 1 一个合法询问都没有 —— 那 300 轮验的全是「Crossing the line」这一行字\n");


    printf("\n② 顶格 n = 1000、m = 10⁶：每询问重扫一遍要扫多少格\n");
    printf("   顶格**随机** %lld 格；顶格**最坏**（全问 [1, m]）%lld 格 ⇒ 差 %.2f 倍\n",
           cellsRnd, cellsWorst, (double)cellsWorst / (double)cellsRnd);
    printf("   秒表（3 次取中位数）：正解 %.0f ms ／ 重扫·随机 %.0f ms ／ 重扫·最坏 %.0f ms\n", mf, mr, mw);
    printf("   ⇒ 重扫版比正解慢 %.1f 倍（随机）／ %.1f 倍（最坏），而时限只有 1 秒\n", mr / mf, mw / mf);


    printf("\n②b 第 ① 版（每个数试除判质数）：一个 [1, 10⁶] 的询问要 %.0f 毫秒 ⇒ 1000 个询问外推 %.0f 秒\n",
           msBruteOne, msBruteOne * N / 1000.0);
    printf("   ⚠ 而题面写着「对于 20%% 的数据，n, m ≤ 10」⇒ **它稳拿 20 分**\n");


    printf("\n③ 读入量：顶格 1000 行询问一共 %lld 字节 ⇒ **读入优化在这道题上一点用都没有**\n", ioBytes);
    return 0;
}
点一下即可编辑
输出
点「运行 ▶」看结果
第 ② 版就能过；而三个错法里，样例只挡住了一个
版本 顶格最坏 交上去
① 每询问逐个试除 外推 约 165 秒 20 分（题面 20% 档 n, m ≤ 10）
★ ② 筛 + 每询问重扫 0.24 秒 ★ AC
★ ③ 筛 + 前缀和 1.3 毫秒 ★ AC
三个错法 官方样例挡得住吗
✗ 1 当成质数 ★ 挡住了（样例第一问就是 l = 1，它打 3 而不是 2）
✗ cnt[r] − cnt[l] ✗ 放过（l = 1 不是质数，这一格本来就不该算）
✗ 越界只判右边 ✗ 放过（样例那个越界是 r > m，恰好是它判了的那一头）

⇒ 又一次「官方样例是个『一测就死』的过滤器」： 挡住的是「每一组都错」的那个，放过的是「偶尔才错」和「结构上碰不到」的那两个。

⚠ 最后一条和算法无关的否定结论：这道题顶格只有 1000 行询问， 输入一共 13 788 字节 ⇒ 读入优化在这道题上一点用都没有 （对照 P2367 的 2 × 10⁷ 个数：连 scanf 都不够 —— 倍数跨题几乎不变，变的是绝对时间）。