同一道题，逻辑完全正确，却被判超时——这大概是竞赛里最让人憋屈的死法。而解法往往不是"想个新算法"，而是"把重复做的那部分删掉"。

🎯 前言

Day 4 我还在琢磨浮点误差和栈的大小，觉得自己对"程序到底在干什么"已经有点底了。Day 5 直接给我来了四个下马威。

第一道：求第 30000 个质数。我写的试除法逻辑上一丝不差——从 2 开始，每个数试除到它自己减一，能整除就不是质数。交上去，TLE。我算了一下，这段代码总共要跑 52.5 亿次运算。而正确解法只要 0.06 秒。

第二道：开关灯。我用 for(j = i; j <= n; j++) if(j % i == 0) 去挑倍数，写得理直气壮——“编号是 i 的倍数”，翻译成代码不就是取模吗？直到我看见 for(j = i; j <= n; j += i) 这一行才反应过来：根本不用判断，步长直接就锁定了目标。

第三道：杨辉三角。我老老实实开了个 arr[25][25] 存完整三角。但第 i 行只依赖第 i-1 行，前面那些行算完就没用了——我存了 20 行，其中 19 行是冗余。

第四道：数组逆序。我用了 while(n > 0) { cout << arr[n-1]; n--; }，能过。但蓝本用两个指针从两端逼近，交换完 n 一点没动。差距不在"能不能过"，而在于前者的 n 被吃掉了，后者的 n 还活着。

这四道题看起来毫不相干，但它们的解法本质是同一句话：找出那些不必要的工作，然后删掉它。试除法在重复判断同一个数，埃氏筛在重复标记同一个合数，欧拉筛把这份重复压到零，步长法删掉了无效的取模判断，滚动数组删掉了冗余的存储，双指针删掉了重复的访问。这篇 Day 5，我就沿着"删除"这条线，把这四种刀法一起梳理一遍。

---

---

一、52.5 亿次运算：试除法为什么会 TLE

题目

求第 n 个质数（洛谷 B2085），n ≤ 30000。

我当时写的骨架

for(int i=1; i<=n; i++) {
    for(int j=2; j<i-1; j++) {
        if(j%i != 0) count++;
    }
    if(i == count) break;
}
cout << count;

这段代码交上去不只是 TLE，是彻底错。三个致命伤：

1. j % i 写反了——应该是 i % j。判断 i 能不能被 j 整除，被除数得是 i。
2. count 从不清零——它在所有 i 之间累加，跨轮污染（正是 Day 4 讲的"状态变量必须清零"）。
3. 外层循环变量用错——外层 i 从 1 数到 n，可 n 是"第几个质数"，不是"数值上限"。第 30000 个质数是 350377，数到 30000 根本没走完。

⚠️ 第 3 条最值得警惕：n 这个字母在这里承担了两种完全不同的语义。它是"要找第 n 个质数"的序号，不是"在 1~n 里找质数"的上界。同一道题里，n 和 i 谁是序号、谁是数值，必须在动手前就分清。

修正后的逻辑

int i = 2;
while (1) {
    bool isPrime = true;
    for (int j = 2; j < i; j++) {      // 试除到 i-1
        if (i % j == 0) { isPrime = false; break; }
    }
    if (isPrime) {
        cnt++;
        if (cnt == n) break;           // 找到第 n 个，停
    }
    i++;
}
cout << i;

这次逻辑对了。但——TLE。

52.5 亿次是怎么算出来的

项	数值
n	30000
第 30000 个质数	约 350377
最坏情况内层循环次数	350377 次
平均（只试除一半）	约 175000 次
总运算量	30000 × 350000 ÷ 2 ≈ 52.5 亿次
计算机每秒能执行	约 10⁸（1 亿）次
预估耗时	约 50 秒
题目限制	1.00 秒

超了 50 倍。这个估算方法很值得记住：先算最坏情况的内层次数，乘上外层次数，除以 10⁸，得到的就是秒数。以后看到 O(n²) 且 n > 10⁴，心里就该有警报。

优化：只试到 √i

for (int i = 2; ; i++) {
    bool isPrime = true;
    for (int k = 2; k * k <= i; k++) {      // 关键：k*k <= i
        if (i % k == 0) { isPrime = false; break; }
    }
    if (isPrime) {
        cnt++;
        if (cnt == n) { cout << i << endl; break; }
    }
}

内层从 350000 次降到 约 591 次（√350000 ≈ 591）。总运算量从 52.5 亿降到百万级别，稳稳通过。

一个我差点踩的坑：靠 j 的退出位置判断

我一开始想省掉 isPrime 变量，用 j 循环结束后的值反推：

int j;
for (j = 2; j * j <= i; j++) {
    if (i % j == 0) break;
}
// 如果 j*j > i，说明循环正常走完 → i 是质数

想法挺妙：质数会让循环正常跑完，j 会停在第一个满足 j*j > i 的位置；合数会被 break 打断，j 停在因子处。

但这里有两个坑：

1. break 出来的 j 和正常退出的 j 可能落在同一个位置。比如 i = 9：j=2 时 4≤9 继续，j=3 时 9%3==0 → break，j 停在 3。此时 3*3=9 不满足 j*j > i，能区分。但换个例子，判断逻辑会变得非常脆弱——只要边界条件差一点就翻车。
2. 可读性彻底崩了。三个月后回看，没人能一眼看懂"为什么 j 的值能说明 i 是质数"。

蓝本的注释写得很实在：“为了判断准确，还是需要一个小逻辑来区分，这里用最稳妥的 isPrime 标记。”

这就是 Day 2.5 讲过的 while(n--) 退出后 n = -1 的同一个道理：依赖循环变量的退出值做判断，是把自己的正确性押在循环边界的精确性上。一个 bool 变量换来的清晰，远比省下那 4 个字节划算。

深度思考：为什么只需试到 √i？如果 i 是合数，它一定有小因子吗？

这是初等数论里最基本也最常被"会用不会证"的一个结论，值得完整推一遍。

定理：若正整数 $n>1$ 是合数，则 $n$ 必有一个质因子 $p\le \sqrt{n}$。

证明：因为 $n$ 是合数，存在分解 $n=a\cdot b$，其中 $1<a\le b<n$。假设 $a>\sqrt{n}$ 且 $b>\sqrt{n}$，则 $a\cdot b>\sqrt{n}\cdot \sqrt{n}=n$，与 $n=ab$ 矛盾。所以必有 $a\le \sqrt{n}$（至少一个因子不超过 $\sqrt{n}$）。

再对 $a$ 做质因数分解：$a$ 的任一质因子 $p$ 都满足 $p\le a\le \sqrt{n}$，且 $p\mid a\mid n$，即 $p$ 也是 $n$ 的质因子。证毕。

这个结论的推论直接给出了算法：要判断 $n$ 是不是质数，只需检查 $2$ 到 $\lfloor \sqrt{n}\rfloor$ 之间有没有 $n$ 的因子。如果这个区间内一个都没有，那么大于 $\sqrt{n}$ 的那部分因子也不可能存在——因为因子总是成对出现的，一个大因子必然配一个小因子，小因子已经被排除了。

举个具体例子：$i=16$，$\sqrt{16}=4$，因子 2 小于 4，一发现 2 能整除 16 就立刻判定不是质数，根本不用试到 15。$i=350377$（第 30000 个质数），$\sqrt{350377}\approx 591.9$，所以只需检查 2 到 591，591 之后的数一个都不用试。

复杂度上，单次判断从 $O(n)$ 降到 $O(\sqrt{n})$，n 次判断的整体从 $O(n^2)$ 降到 $O(n\sqrt{n})$。这个量级对 30000 个数（约 350000 上限）刚好够用，但如果数据继续涨到 10⁷、10⁸，$O(n\sqrt{n})$ 依然会崩——那就需要换筛法了。

还有一个工程细节：k * k <= i 比 k <= sqrt(i) 更好。前者是纯整数运算，零误差；后者要调 sqrt，引入浮点，还得防 Day 4 讲过的精度问题（比如 sqrt 返回 590.9999999 导致少试一次）。竞赛里能用整数比较就别用浮点。

📖 结论：合数必有一个不超过 $\sqrt{n}$ 的质因子（因子成对 + 反证法），因此试除只需进行到 $\lfloor \sqrt{n}\rfloor$；单次判断复杂度 $O(\sqrt{n})$；用 k*k <= i 而非 k <= sqrt(i) 可彻底规避浮点误差。

---

二、埃氏筛：从"逐个判断"到"批量划掉"

换个思路：不判断，只划掉

试除法的思路是"对每个数，问它是不是质数"。埃氏筛的思路完全反过来：

对每个质数，把它所有的倍数划掉。

这两种思路的差别，就像"逐个检查每个人有没有犯罪记录"和"把有前科的人的亲戚全标记一遍"——后者一次操作能处理一大片。

筛子的五步

想象你有一张写着 2, 3, 4, 5, …, 400000 的纸条：

1. 默认全是质数——先假设纸条上所有数字都是质数。
2. 从最小的质数开始：找到第一个质数 2，把 2 的所有倍数（4, 6, 8, 10…）全部划掉（它们一定是合数）。
3. 找下一个没被划掉的数：跳过 3？不，3 没被划掉，所以 3 是质数。把 3 的所有倍数（6, 9, 12, 15…）全部划掉。
4. 继续：跳过 4（已被划掉，说明它是合数）。找到 5，把 5 的倍数全划掉。
5. 终点：一直筛到上限。纸条上最后剩下的，全都是质数！

这就像一把筛子，孔的大小从 2 开始、3 开始，把合数一层层漏下去，最后留下的就是质数。

代码

#include <iostream>
using namespace std;

bool is_prime[400005];      // 全局数组，默认全 false

int main() {
    int n;
    cin >> n;

    // 初始化：先假设从 2 开始的所有数字都是质数（标记为 true）
    for (int i = 2; i <= 400000; i++) {
        is_prime[i] = true;
    }

    int cnt = 0;

    // 开始"筛"
    for (int i = 2; i <= 400000; i++) {
        if (is_prime[i] == true) {          // i 没被筛掉 → 是质数
            cnt++;
            if (cnt == n) {                 // 找到第 n 个质数
                cout << i << endl;
                break;
            }
            // 核心操作：把 i 的所有倍数全部标记为非质数
            for (long long j = 1LL * i * i; j <= 400000; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return 0;
}

神来之笔一：内层从 i * i 开始，不是 i * 2

这是埃氏筛最反直觉、也最关键的一处优化。为什么可以跳过 2*i 到 (i-1)*i 这一段？

假设当前质数 i = 5，要筛掉的倍数是 10, 15, 20, 25, 30, 35, 40…

倍数	分解	谁筛的
10	2 × 5	i = 2 时，作为 2 的倍数已筛
15	3 × 5	i = 3 时，作为 3 的倍数已筛
20	4 × 5 = 2 × 10	i = 2 时，作为 2 的倍数已筛
25	5 × 5	前面 2、3 都筛不掉它——因为 25 的最小质因子就是 5

核心数学原理：如果一个合数 $x$ 能被质数 $i$ 整除，即 $x=a\cdot i$。

• 如果 $a<i$，那么 $a$ 一定有一个比 $i$ 小的质因子（或者 $a$ 本身就是比 $i$ 小的质数）。
• 这意味着 $x$ 在遇到质数 $i$ 之前，早就被更小的质数 $a$ 给筛掉了。
• 所以当我们用质数 $i$ 去筛时，只需要从 $a=i$ 开始，也就是从 $x=i\cdot i$ 开始筛，才不会做无用功。

一句话总结：i*i 之前的倍数，已经被更小的质数筛过了，重复筛就是浪费。

神来之笔二：外层筛到哪

题目说 n ≤ 30000，根据数学计算，第 30000 个质数大约在 350377。为了保险，直接把数组开到 400000。

这就是"空间换时间"：多开 40 万个 bool（约 400KB），换来整个算法的可行性。

💡 如果不知道上限怎么办？开大一点（比如 1000000）就行，bool 数组很便宜。但如果开到 10⁸，那就是 100MB，直接 MLE 了——这个边界后面会详细讲。

一个蓝本代码里藏着的 UB：i * i 会溢出

蓝本的原始代码是：

for (int j = i * i; j <= 400000; j += i) {     // ⚠️ 危险
    is_prime[j] = false;
}

看起来没问题，但我盯着想了半天：外层 i 会一直走到 400000，那 i = 350377 时，i * i 是多少？

$$350377^2\approx 1.23\times 10^{11}$$

而 int 的上限是 $2.1\times 10^9$。溢出十倍以上。

溢出的后果不是简单变负数——C++ 里有符号整数溢出是 未定义行为（UB），编译器可以做任何事。实际常见的表现是：i*i 变成一个负数或奇怪的小正数，j 从那个值开始，j <= 400000 判定为真，循环进入，然后 is_prime[j] 用负下标访问数组——越界。

正确写法有两种：

// 写法 A：把 j 声明为 long long（推荐，改动最小）
for (long long j = 1LL * i * i; j <= 400000; j += i) {
    is_prime[j] = false;
}

// 写法 B：加个守卫，i*i 超出范围就别筛了
if (1LL * i * i > 400000) continue;
for (int j = i * i; j <= 400000; j += i) {
    is_prime[j] = false;
}

写法 A 里 1LL * i * i 的意思是：先把 i 提升成 long long 再乘，这样乘法在 64 位下进行，不会溢出。

⚠️ 这是个特别容易漏的坑，因为它不一定报错。很多评测机上溢出的负数恰好越界后没触发段错误，程序"看起来能跑"，但某些数据下就突然 RE 或者答案错误。这种间歇性 bug 最难查。

记住一条：只要写 i * i，先问一句"i 最大能到多少，平方会不会超 int"。

埃氏筛的三大坑

蓝本总结得很到位，我原样记下：

坑 1：0 和 1 不是质数。 我们的初始化从 i = 2 开始设置 true，所以 is_prime[0] 和 is_prime[1] 保持默认的 false（非质数），这是正确的。如果手贱写了 for (int i = 0; ...)，就会把 0 和 1 当成质数。

坑 2：数组大小一定要开够。 如果只开 30000 大小的数组，去求第 30000 个质数（大约 35 万），程序会发生数组越界（RE），直接崩溃。开数组要按"值的范围"开，不是按"个数"开。

坑 3：重复标记问题。 比如 6，被 2 筛了一次，又被 3 筛了一次。这就是埃氏筛无法做到完美 $O(N)$ 的原因——后面欧拉筛会解决它。

埃氏筛什么时候用、什么时候别用

✅ 该用	场景
求范围质数 / 第 N 个质数	洛谷 B2085，或题目给出明确上限（N ≤ 10⁶ 或 10⁷）
海量查询	10⁵ 次查询"x 是不是质数"，筛法预处理一次后每次 O(1)
质因数分解预处理	先把范围内质数全筛出，再用这些质数去试除大数，效率极高

竞赛经验法则：

• $N\le 10^6$：直接用。
• $N\le 10^7$：可以用，但注意内存（bool 数组约 10MB）。
• $N\le 10^8$：非常勉强，需使用 bitset 优化（每个元素压到 1 bit，内存降到 12.5MB）。
• $N\ge 10^9$：千万别用，10⁹ 个 bool 直接占 1GB，MLE 必死。此时应该用区间筛法或 Min_25 筛。

❌ 别用	原因
只判断"一个数"	判断 10⁹+7 是不是质数，用筛法是"杀鸡用牛刀"，直接 O(√n) 试除瞬间出结果
超大数判断（N ≥ 10¹²）	筛法完全无能为力，必须用 Miller-Rabin 概率性素性测试
空间极度受限	如单片机只有几 KB 内存，只能试除法，用时间换空间

终极实战口诀：

“范围小，数量多，找质数，用筛法；范围大，次数少，单判断，用试除。”

实战：海量质数查询系统

题目：系统接收 Q 次查询（Q = 100,000），每次给出整数 X（X ≤ 1,000,000），立刻回答是否为质数。

如果每次都用试除法：

• 每次查询最坏需要试到 √10⁶ = 1000
• 总运算量 = 100,000 × 1000 = 10⁸（1 亿次）
• 在 1 秒限制下极其危险，大概率 TLE

用埃氏筛： 程序启动时先花几十毫秒把 1~10⁶ 内所有质数筛出来，然后每次查询 O(1)。

#include <iostream>
using namespace std;

bool is_prime[1000005];

int main() {
    int Q;
    cin >> Q;

    // 1. 预处理：用埃氏筛出 1~1000000 的所有质数
    for (int i = 2; i <= 1000000; i++)
        is_prime[i] = true;

    for (int i = 2; 1LL * i * i <= 1000000; i++) {     // 外层只需到 √N
        if (is_prime[i] == true) {
            for (long long j = 1LL * i * i; j <= 1000000; j += i)
                is_prime[j] = false;
        }
    }

    // 2. 处理查询：O(1) 极速响应
    for (int k = 0; k < Q; k++) {
        int x;
        cin >> x;
        if (is_prime[x] == true) cout << x << " 是质数" << endl;
        else cout << x << " 不是质数" << endl;
    }
    return 0;
}

效果对比：

• 预处理时间：不到 0.05 秒
• 单次查询时间：O(1)
• 总时间：0.05 秒 + 100,000 × O(1) ≈ 0.06 秒
• 直接完美 AC，毫无超时压力

这就是埃氏筛最经典的实战应用——“一次预处理，万次秒查询”。

💡 注意这里外层循环写的是 1LL * i * i <= 1000000，只到 1000 就够了。为什么？因为 i > √N 时，i*i > N，内层循环一次都不会执行。而且这么写还顺手避开了 i*i 溢出的问题——i 最大才 1000，平方是 10⁶，安全。

这也是一个重要的写法选择：求"第 n 个质数"时必须遍历到 N（因为要数质数），但求"范围内所有质数"时外层到 √N 就够。两者别混。

深度思考：为什么从 i*i 开始筛是正确的？为什么总复杂度是 N log log N 而不是 N²？

需要把"正确性"和"复杂度"分开论证。

正确性：i*i 之前的倍数为什么可以不筛？

要证明的是：对任意质数 $i$，任何形如 $a\cdot i$（$a<i$）的合数，都已经在更早的步骤中被筛掉了。

因为 $a<i$，对 $a$ 做质因数分解，设其最小质因子为 $q$。显然 $q\le a<i$。于是 $a\cdot i=q\cdot \left(\frac{a}{q}\cdot i\right)$，即这个数可以写成"$q$ 的某个倍数"。而在处理质数 $q$ 的那一轮（$q<i$，必然更早发生），我们已经把所有 $q$ 的倍数标记为合数了——只要那个倍数 $\ge q^2$。

需要确认 $a\cdot i\ge q^2$：因为 $a\ge q$（$q$ 是 $a$ 的因子且 $a\ge 1$）且 $i>q$，所以 $a\cdot i>q\cdot q=q^2$。✅ 条件满足。

因此 $a\cdot i$ 在 $q$ 那一轮就被筛掉了，$i$ 这一轮从 $i^2$ 开始完全正确。这不是一个"近似优化"，而是严格无损的。

复杂度：为什么是 $N\log \log N$？

总操作次数等于"对每个质数 $p$，执行 $\frac{N}{p}-p$ 次标记"，近似为 ${\sum }_{p\le N}\frac{N}{p}=N{\sum }_{p\le N}\frac{1}{p}$。

而质数倒数和有一个经典结论（Mertens 第二定理）：${\sum }_{p\le N}\frac{1}{p}\approx \ln \ln N+M$（$M\approx 0.2615$ 是 Meissel–Mertens 常数）。

所以总复杂度是 $O(N\log \log N)$。$\log \log N$ 增长极慢：$N=10^6$ 时 $\log \log N\approx 2.6$，$N=10^8$ 时也只有约 3.0。这就是为什么埃氏筛"看起来是两层循环"却快得离谱——内层循环的总执行次数只比 N 多几倍，不是 N²。

N	N log log N 的系数	实际标记次数约
10⁶	≈ 2.6	约 2.6×10⁶
10⁷	≈ 2.8	约 2.8×10⁷
10⁸	≈ 3.0	约 3.0×10⁸

对比一下：如果从 2*i 开始筛（不优化），总次数是 $N{\sum }_p\frac{1}{p}-{\sum }_{p}p$，差别在低阶项，量级仍是 $N\log \log N$，但常数大不少——所以 i*i 优化主要是砍常数，不是改量级。真正改变量级的是欧拉筛。

📖 结论：i*i 起点的正确性由"合数必有更小质因子"保证（严格无损，非近似）；埃氏筛总标记次数为 ${\sum }_{p\le N}N/p=N{\sum }_{p\le N}1/p\approx N\ln \ln N$，故复杂度 $O(N\log \log N)$，其中 $\log \log N$ 增长极缓，这正是筛法远快于直觉的原因。

---

三、欧拉筛：让每个合数只死一次

埃氏筛的痛点

埃氏筛已经很快了，但它有一个致命的缺点：一个合数会被重复筛掉（重复标记）。

比如合数 12：

• 当 i = 2 时，12 作为 2 的倍数被筛掉一次。
• 当 i = 3 时，12 作为 3 的倍数又被筛掉一次。

同一个 12，被筛了两遍。 虽然埃氏筛已经很快，但在极限数据（如 N = 10⁸）下，这种重复标记依然会浪费宝贵的时间。

欧拉筛的承诺：每个合数，只会被它的"最小质因子"筛掉，且仅被筛掉一次。 只要做到这一点，时间复杂度直接降为完美的 $O(N)$。

核心代码

欧拉筛的代码极其巧妙，它需要额外维护一个数组 primes 来记录已经找到的质数：

#include <iostream>
using namespace std;

bool not_prime[1000005];     // true = 已被筛掉（合数）
int primes[1000005];         // 存储找到的质数
int cnt = 0;                 // 记录当前找到了几个质数

int main() {
    int n;
    cin >> n;

    // 从 2 开始遍历
    for (int i = 2; i <= n; i++) {
        // 如果 i 没被筛掉，说明它是质数
        if (not_prime[i] == false) {
            primes[cnt++] = i;              // 存入 primes 数组
        }

        // 核心代码：用当前找到的质数去筛后面的合数
        for (int j = 0; j < cnt; j++) {
            int p = primes[j];              // 取出一个质数 p
            if (1LL * i * p > n) break;     // 越界了，停止
            not_prime[i * p] = true;        // 将 i * p 标记为合数
            // 🌟 欧拉筛的灵魂：保证每个合数只被它的最小质因子筛掉
            if (i % p == 0) break;
        }
    }

    // 输出 1~n 之间的所有质数
    for (int i = 0; i < cnt; i++) {
        cout << primes[i] << " ";
    }
    return 0;
}

灵魂拷问：if (i % p == 0) break; 为什么这么神奇

假设当前外层 i = 12，primes 数组里有 [2, 3, 5, 7, 11]。

1. j = 0, p = 2：筛掉 12 * 2 = 24。此时判断 12 % 2 == 0 成立，触发 break！后面的 p = 3, 5… 全都不执行了。

2. 为什么？ 因为 24 = 12 * 2，24 的最小质因子是 2。如果我们继续用 p = 3 去筛 12 * 3 = 36，那 36 的最小质因子也是 2，它应该在 i = 18 时被 p = 2 筛掉（18 * 2 = 36），而不是在 i = 12 时被 p = 3 筛掉。

3. 通过 break，我们强制规定：每个合数 i * p，必须在 p 是 i 的最小质因子时，才被筛掉。

数学证明：

• 设 $i=a\cdot p$（$p$ 是质数，且 $p$ 是 $i$ 的最小质因子）。
• 当 i % p == 0 时，说明 $p$ 是 $i$ 的因子，且因为 primes 数组是递增的、我们是从小到大枚举 $p$，所以 $p$ 一定是 $i$ 的最小质因子。
• 此时我们要筛的下一个数是 $i\cdot p_{next}$（$p_{next}$ 是比 $p$ 大的质数）。这个数的因子包含 $p_{next}$ 和 $i$，而 $i$ 的最小质因子是 $p$，所以 $i\cdot p_{next}$ 的最小质因子是 $p$。
• 那么 $i\cdot p_{next}$ 应该由 $\left(\frac{i}{p}\cdot p_{next}\right)\cdot p$ 来筛掉，而不是现在由 $i\cdot p_{next}$ 来筛。

换句话说：如果现在不 break，那这个数将来会以另一种形式被更小的质因子筛到，现在就筛属于"抢跑"，会造成重复。

一个严重的命名坑：is_prime 的 true 竟然是合数

蓝本原始代码是这样的：

bool is_prime[100000005];    // 注释写的是"标记是否为质数"

for (int i = 2; i <= n; i++) {
    if (is_prime[i] == false) {      // false → 是质数？？
        is_prime[i] = true;          // 把质数标记成 true？？
        primes[cnt++] = i;
    }
    for (int j = 0; j < cnt; j++) {
        int p = primes[j];
        if (i * p > n) break;
        is_prime[i * p] = true;      // 把合数也标记成 true
        if (i % p == 0) break;
    }
}

我第一遍读这段代码时彻底懵了：is_prime[i] == false 说明 i 是质数，然后立刻 is_prime[i] = true；而 is_prime[i * p] = true 又把合数设成 true。那 true 到底是质数还是合数？

答案是：true 表示"已经被处理过"，跟质数与否毫无关系。

• 质数 i 被"处理"的方式是加入 primes 数组，所以标记为 true。
• 合数 i * p 被"处理"的方式是被筛掉，也标记为 true。
• 两者共用 true，是为了让 if (is_prime[i] == false) 这个判断能识别"还没被碰过的 i"——只有没被碰过的才是质数。

逻辑上它是对的，但命名上是灾难。 因为变量名叫 is_prime，注释写"标记是否为质数"，而 true 的实际语义是"非质数 / 已处理"。这种命名与语义的背离，在调试时会让人疯掉——你会对着 is_prime[i] == true 想半天"为什么质数要设成 true"。

正确做法是把名字改成它真正的语义：

bool not_prime[1000005];     // true = 已被筛掉（合数）
int primes[1000005], cnt = 0;

for (int i = 2; i <= n; i++) {
    if (!not_prime[i]) {                 // 没被筛掉 → 是质数
        primes[cnt++] = i;
    }
    for (int j = 0; j < cnt; j++) {
        int p = primes[j];
        if (1LL * i * p > n) break;
        not_prime[i * p] = true;         // 标记合数
        if (i % p == 0) break;
    }
}

改完之后，if (!not_prime[i]) 读起来就是"如果 i 不是合数"，not_prime[i*p] = true 就是"把 i*p 标记为合数"，语义完全自洽，再也不用在脑子里做反向翻译。

💡 这条经验很值钱：变量名必须和它的实际语义一致，而不是和它的"预期用途"一致。当你发现自己在写 is_prime[x] = true 表示"x 不是质数"时，就该立刻停下改名字——否则这个 bug 会以"逻辑没错但结果诡异"的形式在三个月后找你算账。

埃氏筛 vs 欧拉筛：终极对比

对比维度	埃氏筛（Eratosthenes）	欧拉筛（Euler / Linear）
时间复杂度	$O(N\log \log N)$	$O(N)$（严格线性）
空间复杂度	$O(N)$	$O(N)$（需额外存质数数组）
重复筛除	有，同一合数可被多个质数筛	无，每个合数只被最小质因子筛一次
代码难度	简单，双重循环	较难，break 条件极难理解
适用场景	$N\le 10^7$ 完全够用，性价比高	$N\le 10^8$ 甚至更大，必须用欧拉筛才稳

那到底该用哪个？

蓝本的建议很实在：

虽然欧拉筛理论复杂度完美，但在洛谷 B2085（第 n 个质数，N ≈ 40 万）这道题里，埃氏筛和欧拉筛跑起来都是 0.00 秒，没有肉眼可见的区别。

• 新手阶段：熟练掌握埃氏筛，理解 i*i 优化，已经能解决 95% 的质数筛问题。
• 进阶阶段：当遇到数据量达到 10⁸，埃氏筛被卡 TLE 时，再掏出欧拉筛。

这个建议我很认同——不要为了"理论上更优"而过早引入复杂度。$O(N\log \log N)$ 和 $O(N)$ 在 10⁶ 量级上差别是毫秒级，而欧拉筛的 if (i % p == 0) break 一旦写错，正确性会全盘崩塌。工程上，能跑对的简单代码 > 看不懂的完美代码。

深度思考：线性筛为什么真的是 O(N)？"每个合数只被最小质因子筛一次"的唯一性怎么证？

这是欧拉筛最核心也最难理解的定理，需要从"表示的唯一性"和"枚举的完备性"两个方向同时论证。

先看埃氏筛为什么做不到：合数 12 = 2×6 = 3×4，在 i=2 和 i=3 两轮都会被标记，重复一次。合数 30 = 2×15 = 3×10 = 5×6，会被标记三次。重复次数等于合数的不同质因子个数，平均约 $\log \log N$ 次——这正是 $N\log \log N$ 的来源。

欧拉筛的核心不变量：每个合数 $x$ 被筛掉时，使用的质数 $p$ 一定是 $x$ 的最小质因子。

证明（唯一性）：设合数 $x$ 的最小质因子为 $p_{\min }$，则 $x=p_{\min }\cdot m$，其中 $m\ge p_{\min }$（否则 $m$ 会有比 $p_{\min }$ 更小的质因子，矛盾）。

欧拉筛在 $i=m$ 这一轮，枚举质数 $p$ 时，必然枚举到 $p=p_{\min }$（因为 $p_{\min }\le m$，而质数是从小到大枚举的）。此时：

• 若在 $p_{\min }$ 之前有更小的质数 $q<p_{\min }$ 被枚举到，会先执行 not_prime[m * q] = true 并检查 m % q == 0。由于 $p_{\min }$ 是 $x=m\cdot p_{\min }$ 的最小质因子，$m$ 的最小质因子 $\ge p_{\min }>q$，所以 $q\nmid m$，m % q != 0，不会 break。
• 枚举到 $p=p_{\min }$ 时，not_prime[m * p_min] = true 成功标记 $x$；此时 $m\%p_{\min }==0$（因为 $p_{\min }\mid m$），触发 break。

所以 $x$ 在 $i=m$、$p=p_{\min }$ 这一轮被标记，且仅被标记这一次——因为 break 之后，$i>m$ 的任何一轮都不会再产生 $x$（$x/i$ 会小于 $p_{\min }$，而枚举的 $p$ 都 $\ge p_{\min }$，$i\cdot p>x$ 或产生的数的最小质因子不是 $p$）。

再看完备性：每个合数都会被筛到吗？是的——任何合数 $x$ 都有最小质因子 $p_{\min }$，都能写成 $m\cdot p_{\min }$，而 $m<x$，所以 $m$ 会在外层循环中被遍历到（$m\ge p_{\min }\ge 2$）。因此每个合数都恰好被覆盖一次。

复杂度：内层循环总共执行多少次？每次执行都标记一个不同的合数（唯一性保证），而合数总数不超过 $N$，所以内层总执行次数 $\le N$。外层 $N$ 次。总计 $O(N)$。这是严格的线性，不是平均意义上的。

一个容易混淆的点：内层循环的 break 看起来像"提前退出可能漏筛"，实际上恰恰相反——break 是保证不漏也不重的前提。如果不 break，$x$ 会被更大的质因子重复筛；如果 break 得太早（比如把条件写成 i % p == 1），就会漏掉那些最小质因子尚未枚举到的合数。

筛法	每个合数的标记次数	总标记次数	复杂度
埃氏筛（2*i 起）	$\omega (x)$（不同质因子数）	$\approx N\log \log N$	$O(N\log \log N)$
埃氏筛（i*i 起）	同上，但常数更小	$\approx N\log \log N$	$O(N\log \log N)$
欧拉筛	恰好 1 次	$\le N$	$O(N)$

📖 结论：欧拉筛通过 if (i % p == 0) break 强制"合数只在其最小质因子那一轮被标记"，由最小质因子的存在性与唯一性保证每个合数恰好标记一次；总标记次数不超过 N，故为严格 $O(N)$；break 不是优化而是正确性条件。

---

四、开关灯：步长代替取模，一次删掉一半循环

题目

有 n 盏灯，编号 1~n。第 1 个人把所有的灯打开（或关闭）；第 2 个人把编号是 2 的倍数的灯状态反转；第 3 个人把编号是 3 的倍数的灯反转……第 i 个人把编号是 i 的倍数的灯反转。问最后有哪些灯是关着的。

我写的版本

int arr[5050] = {0};        // 0 表示关

int main() {
    int n;
    cin >> n;

    for (int i = 2; i <= n; i++) {          // i 是人的编号
        for (int j = i; j <= n; j++) {      // j 是灯的编号
            if (j % i == 0) {               // ⚠️ 逐个判断是不是倍数
                arr[j] = !arr[j];
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (arr[i] == 0) cout << i << " ";
    }
    cout << endl;
    return 0;
}

逻辑完全正确：内层遍历所有灯，用 j % i == 0 挑出 i 的倍数，翻转状态。arr[j] = !arr[j] 也比 if-else 干净得多。

但这段代码里藏着一个巨大的浪费：内层循环跑了 n 次，其中只有 1/i 的比例是真正需要处理的。

i = 2 时，只有一半的灯是 2 的倍数；i = 100 时，只有 1% 的灯是 100 的倍数。剩下的 99% 全都在做一件事——判断完之后发现"不是我"，然后跳过。

优化：用步长直接锁定目标

int lights[5050] = {0};

int main() {
    int N;
    cin >> N;

    // 第1个人（i=1）已经把所有灯变成了0（关），所以从第2个人开始模拟
    for (int person = 2; person <= N; person++) {
        // 步长法：直接定位到 person 的倍数，完美跳过不是倍数的灯
        for (int light_id = person; light_id <= N; light_id += person) {
            lights[light_id] = !lights[light_id];   // 状态取反（0变1，1变0）
        }
    }

    for (int i = 1; i <= N; i++) {
        if (lights[i] == 0) cout << i << " ";
    }
    cout << endl;
    return 0;
}

light_id += person 这一行，就是全部的区别。

从 light_id = person 出发，每次跳 person 步，落点必然是 person 的倍数。不需要判断，直接精准命中目标。

两种写法的差距到底多大

写法	内层循环次数（i 这一轮）	有效操作	无效判断
j++ + if (j%i==0)	$N-i+1$	$\lfloor N/i\rfloor$	$N-i+1-\lfloor N/i\rfloor$
j += i	$\lfloor N/i\rfloor$	$\lfloor N/i\rfloor$	0

总次数：

• 原版：${\sum }_{i=2}^N(N-i+1)\approx \frac{N^2}{2}$
• 优化版：${\sum }_{i=2}^N\frac{N}{i}\approx N\ln N$

N = 5000 时：原版约 1250 万次判断，优化版约 4.2 万次操作。差了近 300 倍。

N = 10⁶ 时：原版约 5×10¹¹ 次（必 TLE），优化版约 1.4×10⁷ 次（0.1 秒）。差了近 3.5 万倍。

💡 说实话：这题 n 只有 5000，原版 1250 万次判断也能在 0.02 秒内跑完，不优化照样 AC。所以这个优化的意义不在"能不能过"，而在于建立条件反射——看到"倍数"两个字，手就该自动写出 j += i，而不是 j++ 加取模。等你遇到 n = 10⁶ 的题，这个反射能救你一命。

四条思想，比代码更值钱

蓝本把这题的收获总结成四条，我觉得比代码本身重要得多：

1. 嵌套循环的本质是"维度分离"

• 时间维度（有先后顺序的人）= 外层 for。
• 空间维度（并列存在的灯）= 内层 for。
• 以后遇到复杂模拟题，先找这两个维度，不要试图把它们揉在一起。

这条点醒我了。之前我写模拟题，经常把"第几个人"和"第几盏灯"混在一个循环里，用一堆 if 去分辨"现在轮到谁"。而正确的做法是先问自己：这件事有几个独立的维度？谁在时间上依次发生，谁在空间上同时存在？ 分清了，两层循环自然就出来了。

2. “步长"替代"取模判断”

• 找倍数：for(j=1; j<=N; j++) if(j%i==0) 是直译数学逻辑。
• 用 for(j=i; j<=N; j+=i) 是算法思维。不需要判断，直接精准锁定目标，代码更短，CPU 执行更快。

“直译数学逻辑"这个说法特别准确。我看到"i 的倍数”，脑子里冒出的第一个词就是"取模等于 0"，然后就照抄成了 j % i == 0。这是在翻译题目，不是在设计算法。 而 j += i 是在利用"倍数的等差性质"——它们间隔恰好是 i，所以可以直接跳。

3. 数组下标的"对齐哲学"

• 题目编号是 1~N 时，直接开 arr[N+1]，把 arr[0] 扔掉。
• 与其费尽心思在循环里写 i-1、j+1 去迎合 0 下标，不如浪费一点空间换取逻辑的绝对清晰。

这条我深有体会。以前总觉得"浪费一个元素"不优雅，非要 arr[i-1] 到处减一，结果每次写循环条件都要在脑子里换算一次"题目编号 = 下标 + 1"，稍不留神就错位。现在我的原则是：题目的编号是什么，数组下标就是什么。 多开一个 int 的成本是 4 字节，少写一次 -1 的收益是整段代码可读。

4. 边界与初始状态的白嫖

• 利用全局数组默认 0 的特性，完美省去"第 1 个人把灯全部关闭"的代码，循环直接从 i = 2 起跑。
• 输出循环从 1 到 N（i <= N），避开无意义的 arr[0]，并确保第 N 盏灯被检查到。

这个"白嫖"很妙：题目说第 1 个人把所有灯关掉，而全局数组默认就是 0（关）。所以第 1 个人的操作已经"免费"完成了，代码里根本不用写。 循环从 i = 2 开始，语义上也更准确——“从第 2 个人开始模拟”。

深度思考：为什么 j += i 能把复杂度从 O(N²) 降到 O(N log N)？"维度分离"的判断标准是什么？

先算复杂度。原版内层固定跑 $N-i+1$ 次，求和得 ${\sum }_{i=2}^N(N-i+1)=\frac{(N-1)N}{2}=O(N^2)$。优化版内层跑 $\lfloor N/i\rfloor$ 次，求和得 ${\sum }_{i=2}^N\frac{N}{i}=N\cdot H_N-N=O(N\log N)$，其中 $H_N={\sum }_{k=1}^{N}1/k\approx \ln N+\gamma$ 是调和数（$\gamma \approx 0.5772$ 是欧拉–马歇罗尼常数）。

关键差别在于：原版把"筛选"和"处理"耦合在同一个循环里——每访问一个元素都要先判断它是不是目标，判断成本与处理成本同阶。而优化版把筛选消灭了：步长本身编码了"这些位置就是目标"这一信息，访问即处理，没有浪费。

这在复杂度理论里对应一个更一般的观察：当枚举的集合具有等差结构（或更一般的可生成结构）时，用"生成器"代替"过滤器"，可以把 $O(N)$ 的扫描降为 $O(|S|)$ 的直接枚举。埃氏筛的 j += i、欧拉筛的 i * p、双指针的 left++，都是这个思想的不同形态——不要遍历全集然后筛选，直接生成目标集。

再谈"维度分离"的判断标准。我总结出三条：

判断依据	说明
是否有先后依赖	后一步依赖前一步的结果 → 时间维度 → 外层
是否同时存在	多个对象在同一时刻并列存在 → 空间维度 → 内层
是否可交换	交换两层的顺序，结果是否不变？不变说明两者正交，可以分离

以开关灯为例：第 i 个人必须在第 i-1 个人之后动手（后者改变的状态是前者的输入），这是时间依赖，必须在外层；而第 i 个人操作时，所有灯都是同时存在的（他可以先开 1 号再开 5 号，也可以反过来），这是空间并列，放内层。

反过来，如果某道题里"人"和"灯"的交互是双向的（灯的状态会影响下一个人做什么），那就不能简单分离成两层循环——这就是为什么"复杂模拟题"难写：维度之间产生了耦合。此时要么用状态机把耦合显式化，要么用事件驱动重排。

一个反例可以加深理解：矩阵转置。ans[j][i] = arr[i][j]，两层循环都是空间维度（行列都同时存在），交换顺序结果完全一样——这正是"可交换 = 正交"的体现。

📖 结论：j += i 把 $O(N^2)$ 的"扫描+筛选"改为 $O(N\log N)$ 的"直接生成"，本质是用等差结构编码目标集；嵌套循环的维度分离判据是"时间依赖（先后）放外层、空间并列（同时）放内层"，当两层可交换时即为正交，可自由拆分。

---

五、杨辉三角：DP 递推与滚动数组

题目

输入 n，输出杨辉三角的前 n 行。

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

我写的版本：老老实实开二维数组

int main() {
    int n;
    cin >> n;
    int arr[25][25] = {0};

    // 设置杨辉三角
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (0 == j || i == j)
                arr[i][j] = 1;
            else
                arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
        }
    }

    // 输出
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

能过。逻辑也没错：边界（每行首尾）赋 1，中间等于"左上方 + 正上方"。

但这版有两个问题：

1. 空间冗余：arr[25][25] 是 $O(n^2)$ 空间。可第 i 行只依赖第 i-1 行——前面那些行算完就没用了，我却把 20 行全存着，其中 19 行是纯冗余。
2. arr[25][25] 开在 main 里是局部数组，在栈上。n 小的时候没事，n 一旦上千（虽然本题 n ≤ 20），立刻爆栈。

优化一：滚动数组，空间 O(n²) → O(n)

既然第 i 行只和第 i-1 行有关，那就只保留一行，每轮在它上面原地更新。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int arr[25] = {0};      // 一维数组，初始全为 0

    arr[0] = 1;             // 杨辉三角第一行只有一个 1，放在索引 0 处
    cout << arr[0] << endl; // 输出第一行

    // i 表示当前正在计算的行号，从 1 开始（因为第 0 行已经输出）
    for (int i = 1; i < n; i++) {
        // 从当前行最大有效索引 i 开始，递减到 1
        for (int j = i; j >= 1; j--) {
            // 更新 arr[j]：此时 arr[j] 和 arr[j-1] 都还是上一行的值
            arr[j] = arr[j] + arr[j-1];
        }
        // 注意：arr[0] 永远是 1，不需要更新

        // 输出当前行的所有数字（索引 0 到 i）
        for (int j = 0; j <= i; j++) {
            cout << arr[j] << " ";
        }
        cout << endl;
    }
    return 0;
}

空间从 $O(n^2)$ 降到 $O(n)$。而且没有额外数组，就是原来那个 arr 在被反复覆盖使用。

关键中的关键：为什么必须从后往前更新

这是整个滚动数组最容易错、也最精妙的地方。我把两种顺序都推演一遍。

假设当前 arr 里存的是上一行数据：[1, 2, 1, 0, 0]，我们要算下一行 [1, 3, 3, 1, 0]。

从小到大（j 从 1 到 i）—— 错误

• j = 1：arr[1] = arr[1] + arr[0] = 2 + 1 = 3
  内存状态变成：[1, 3, 1, 0, 0]
• j = 2：arr[2] = arr[2] + arr[1] = 1 + 3 = 4 ← 错了！

期望的 arr[1] 应该是上一行的 2，但它在 j=1 时已经被覆盖成当前行的 3 了。用被污染的数据算，结果自然错。

正确结果应该是 1 + 2 = 3，我却算成了 1 + 3 = 4。

从大到小（j 从 i 到 1）—— 正确

初始 arr 仍是 [1, 2, 1, 0, 0]：

• j = 2（最后一位有效数字）：arr[2] = arr[2] + arr[1] = 1 + 2 = 3
  内存状态：[1, 2, 3, 0, 0]
  注意此时 arr[1] 和 arr[0] 依然是旧值。
• j = 1：arr[1] = arr[1] + arr[0] = 2 + 1 = 3
arr[1] 和 arr[0] 都还是上一行的值，没有被提前修改，计算正确。

最终数组变为 [1, 3, 3, 0, 0]，正是杨辉三角的第三行。

根本原因：arr[j] 的新值依赖 arr[j] 和 arr[j-1] 的旧值。逆序遍历时，计算 arr[j] 的那一刻，arr[j-1] 还没被处理（它在后面才轮到），所以仍是旧值 ✅。而正序遍历时，arr[j-1] 早已被更新成新值了 ❌。

和 Day 4 的双数组对照：同一个敌人，两种打法

这一处让我突然想起了 Day 4 的图像模糊题。那题也是"新值依赖旧值"，解法是开两个数组，读写分离。而这里只用一个数组，靠逆序就解决了。

为什么一个要双数组，一个能省掉？

	Day 4 图像模糊（B2108）	Day 5 杨辉三角
依赖关系	ans[i][j] 依赖5 个邻居：(i,j)、(i-1,j)、(i+1,j)、(i,j-1)、(i,j+1)	arr[j] 只依赖2 个：(j)、(j-1)
逆序能解决吗？	❌ 不能。依赖跨越了"上下两行"，无论怎么排顺序，总有邻居已被更新	✅ 能。依赖只跨"相邻两个位置"，逆序能保证 j-1 尚未被碰
解法	双数组（空间换正确性）	逆序更新（顺序换空间）

这个对照非常值钱：同一个"读后写冒险（RAW）"，能不能靠调整遍历顺序解决，取决于依赖的跨度。

• 依赖只在"相邻位置"、且方向单一 → 逆序更新就能救，省掉一个数组。
• 依赖跨越"多个方向"或"多层结构" → 顺序怎么排都救不了，必须物理隔离（双数组）。

背包问题的一维优化也是同一个道理：dp[j] = max(dp[j], dp[j-w] + v) 必须 j 从大到小遍历，因为 dp[j-w] 要用旧值；而完全背包恰好要从小到大，因为允许同一物品重复用——遍历方向本身就在编码语义。

优化二：组合数公式，连数组都不要

杨辉三角第 i 行第 j 列（都从 0 开始计数）的值，其实就是组合数 $C_i^j$。

既然能直接算，为什么还要存？用递推公式直接计算下一个值：

$$C_i^{j+1}=C_i^j\times \frac{i-j}{j+1}$$

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        long long val = 1;              // 每行第一个数 C(i,0) 恒为 1
        for (int j = 0; j <= i; j++) {
            if (j > 0) cout << " ";     // 格式控制：不是第一个数字时，先输出一个空格
            cout << val;
            // 递推公式：先乘后除，不能先除后乘
            val = val * (i - j) / (j + 1);
        }
        cout << endl;
    }
    return 0;
}

空间复杂度直接降到 O(1) —— 一个 val 变量就够了，连数组都不需要。这就是 Day 4 讲的"不存的艺术"的极致形态。

公式怎么来的

$$C_i^j=\frac{i!}{j!\times (i-j)!},C_i^{j+1}=\frac{i!}{(j+1)!\times (i-j-1)!}$$

两者相除：

$$\frac{C_i^{j+1}}{C_i^j}=\frac{j!\times (i-j)!}{(j+1)!\times (i-j-1)!}=\frac{i-j}{j+1}$$

移项即得 $C_i^{j+1}=C_i^j\times \frac{i-j}{j+1}$。

代入第 5 行验证（i = 5）

j	计算	结果	实际 $C_5^j$
0	初始 val = 1	1	1 ✅
1	1 × (5-0)/(0+1) = 1 × 5	5	5 ✅
2	5 × (5-1)/(1+1) = 5 × 4/2	10	10 ✅
3	10 × (5-2)/(2+1) = 10 × 3/3	10	10 ✅
4	10 × (5-3)/(3+1) = 10 × 2/4	5	5 ✅
5	5 × (5-4)/(4+1) = 5 × 1/5	1	1 ✅

完全对上。

两个必须注意的点

① 必须先乘后除，顺序不能反

val = val * (i - j) / (j + 1);     // ✅ 正确
val = val / (j + 1) * (i - j);     // ❌ 错误

原因：C++ 的整数除法向零截断（Day 4 讲过）。

拿具体例子：val = 5、i - j = 4、j + 1 = 2。

• 先乘后除：5 × 4 / 2 = 20 / 2 = 10 ✅
• 先除后乘：5 / 2 = 2（截断！），2 × 4 = 8 ❌

为什么先乘一定安全？ 因为组合数有个性质：$C_i^j\times (i-j)$ 一定能被 $(j+1)$ 整除，结果就是 $C_i^{j+1}$，本身是整数。所以先做乘法不会损失精度，除法一定能除尽。

② long long 是必须的

虽然本题 n ≤ 20，最大数 184756，int 完全够存。但中间过程 val * (i - j) 会先算乘法——如果 n 更大（比如 n = 30），组合数达到 1.5 亿，中间乘积轻易超过 int 上限 21 亿，直接溢出。

⚠️ 注意这里有个隐蔽的地方：最终结果没超，中间结果超了。这种溢出最难发现，因为小数据测试全对，大数据突然变负。用 long long 兜底，成本是 4 字节。

三个版本横向对比

版本	空间	时间	优点	缺点
二维数组递推	$O(n^2)$	$O(n^2)$	直观，最好理解	空间浪费大，局部数组易爆栈
一维滚动数组	$O(n)$	$O(n^2)$	空间降一个量级，仍是纯加法	必须逆序，顺序写错就崩
组合数递推	$O(1)$	$O(n^2)$	空间最优，不需数组	有乘除法，溢出风险，可读性差

该用哪个？ 我的判断：

• 要输出整个三角 → 用滚动数组（组合数版虽然空间更省，但每行都要重算，且代码不直观）。
• 只要第 n 行 → 用组合数版（连前 n-1 行都不用算，直接算第 n 行，还省时间）。
• 要后续查询任意位置的值 → 老实存二维数组（滚动数组会把历史行覆盖掉）。

这就是 Day 4 那句判断标准的又一次应用：算完之后还需不需要回头看这份数据？

深度思考：滚动数组为什么能压缩空间？逆序更新的本质是什么？组合数递推的整除性怎么保证？

一、滚动数组能成立的充要条件是"有限历史依赖"

滚动数组本质是把 DP 的状态维度按"只保留仍被需要的历史"进行裁剪。形式化地说，若状态转移满足 $f_i=g(f_{i-1})$（第 i 层只依赖第 i-1 层，且不依赖更早的层），那么计算完第 i 层后，第 i-2 层及之前的所有数据都永久失效，可以立即覆盖。

杨辉三角恰好满足：$a[i][j]=a[i-1][j-1]+a[i-1][j]$，右端只出现 $i-1$，没有 $i-2$。所以一个长度为 n 的一维数组就够——它在第 i 轮扮演"第 i-1 行"的角色，在第 i+1 轮扮演"第 i 行"。

反例：如果转移是 $a[i]=a[i-1]+a[i-2]$（斐波那契），就只需要两个变量滚动，而不是一行——保留多少历史，取决于转移式里出现的最大回溯深度。这就是"滚动数组长度 = 依赖跨度"的一般原则。

二、逆序更新的本质是"防止原地覆盖导致读脏数据"

这是一次典型的读后写冒险（RAW hazard）。arr[j] = arr[j] + arr[j-1] 这条语句，需要读 arr[j]（旧）和 arr[j-1]（旧），写 arr[j]（新）。冲突发生在：arr[j-1] 既是本轮某个计算的写目标（当 j’ = j-1 时），又是本轮的读源。

若正序遍历，处理 j 时 j-1 已经写过，读到的是新值 → 错。若逆序遍历，处理 j 时 j-1 尚未轮到 → 读到的还是旧值 → 对。

逆序之所以可行，依赖于"写位置在下标上严格大于读位置"这一方向性。如果转移式变成 arr[j] = arr[j] + arr[j+1]（依赖右侧邻居），那逆序反而会错，必须正序。顺序的方向永远与依赖的方向相反——这是可以机械判断的规则。

而当依赖是多维、多方向的（如 Day 4 图像模糊的上下左右 5 邻居），一维的顺序调整无法同时满足所有方向的"未写"要求，此时必须物理隔离成两个数组。这就是"逆序 vs 双数组"的分水岭。

三、组合数递推的整除性

需要证明 $C_i^j\cdot (i-j)$ 能被 $(j+1)$ 整除。

因为 $C_i^{j+1}=C_i^j\cdot \frac{i-j}{j+1}$ 本身是整数（组合数的定义保证），所以 $C_i^j\cdot (i-j)=C_i^{j+1}\cdot (j+1)$，右端显然是 $(j+1)$ 的整数倍。证毕。

换个角度：这也等价于组合数的整数性——$\frac{i!}{j!(i-j)!}$ 是整数，是因为 $i!$ 中因子 $(j+1)$ 的重数不少于 $j!$ 中的重数（Legendre 公式可证）。总之，"先乘后除"不是碰运气，而是有整除性保证的。

但要注意：这个保证只在中间结果不溢出的前提下成立。如果 val * (i-j) 溢出 long long，即使数学上能除尽，实际算出来也是错的。所以大 n 场景下还得用模运算或高精度。

压缩手段	空间	前提	风险
二维全存	$O(n^2)$	无	无
滚动一维	$O(n)$	依赖跨度 = 1 层	逆序写反
双变量滚动	$O(1)$	依赖跨度 = 2 项	顺序写反
公式直算	$O(1)$	有闭式/递推公式	溢出、整除性

📖 结论：滚动数组的长度等于 DP 转移式的历史回溯跨度；逆序更新的合法性要求"写位置下标严格大于读位置下标"，即遍历方向必须与依赖方向相反；组合数递推先乘后除的安全性由 $C_i^{j+1}(j+1)=C_i^j(i-j)$ 的整除性保证，但仍需防中间乘积溢出。

---

六、双指针：用两个游标换掉一层循环

题目

输入 n 个整数，把它们逆序输出。

我最初的写法

int n = 0;      // 定义在全局
int main() {
    cin >> n;
    const int N = 100;
    int arr[N];
    for (int i = 0; i < n; i++) cin >> arr[i];

    while (n > 0) {
        cout << arr[n-1] << " ";
        n--;        // ⚠️ 注意这里改变了 n 的值
    }
    return 0;
}

能过。输出也对。但我后来才意识到这段代码埋了一个雷：n 被吃掉了。

while (n > 0) { ...; n--; } 循环结束时，n 变成了 0。如果后面还有逻辑——比如再打印一次数组、或者求逆序后前几个数的和——你就没有长度可用了。而且因为 n 是全局变量，它被改成 0 这件事会传播到所有使用它的地方（Day 4 讲过的全局变量污染）。

正解：双指针原地交换

#include <iostream>
using namespace std;

const int N = 110;      // 题目 n 最大为 100，开 110 留有余量，避免越界
int arr[N];             // 全局区声明数组

int main() {
    int n = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 交换
    int left = 0;           // 左指针，指向第一个元素
    int right = n - 1;      // 右指针，指向最后一个元素

    while (left < right) {
        int tmp = arr[left];        // 经典三变量交换
        arr[left] = arr[right];
        arr[right] = tmp;

        left++;                     // 左指针右移
        right--;                    // 右指针左移
    }

    // 输出
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

这个版本好在哪：六个层面

1. 真正的"原地算法"（In-place Algorithm），空间 O(1)

它没有申请任何新数组，只借助了一个额外临时变量 tmp，直接在原数组上完成逆序重排。如果数组有 100 万个元素，这种做法几乎不占额外内存，空间效率满分。

2. 时间 O(n)

while 循环只执行了 $n/2$ 次（两个指针向中间逼近）。加上输入和输出的两个 O(n) 循环，总时间复杂度是线性的 O(n)——这是解决此类问题的最优时间复杂度。

3. 保护了原始变量 n（极其重要）

注意看，输出循环里条件依然是 i < n。这意味着变量 n 的值从头到尾没有被修改。这是一个非常好的编程习惯——如果后续还有逻辑（比如再打印一次数组，或者求逆序后的某几个数之和），你的 n 依然是有效的。

相比之下，我那个 while(n>0) n-- 版本会直接破坏 n 的值，导致后续无法复用。

4. 内存分配规范（全局数组的优势）

int arr[N]; 写在了 main 函数外面：

• 局部数组（写在 main 里）分配在**栈（Stack）上，栈空间很小（通常只有几 MB），数组开太大（比如 10 万）会导致栈溢出（Stack Overflow）**程序崩溃。
• 全局数组（写在 main 外）分配在静态存储区，空间很大。这是算法竞赛中的基操。

（这条正是 Day 4 详细拆过的：栈 8MB vs .bss 几百 MB。）

5. 边界处理极其严谨

while (left < right) 的终止条件非常准确：

• 偶数长度（如 4）：交换 (0,3)、交换 (1,2)，此时 left=2, right=1，2 < 1 为假，循环自然终止。
• 奇数长度（如 5）：交换 (0,4)、交换 (1,3)，此时 left=2, right=2，2 < 2 为假，循环终止。最中间的元素不需要自己和自己交换。

如果写成 left <= right 会怎样？ 奇数长度时，left == right == 2 会让循环再跑一轮，执行 tmp = arr[2]; arr[2] = arr[2]; arr[2] = tmp;——自己和自己交换，结果不变，看似无害。但如果是更复杂的双指针场景（比如带条件移动的滑动窗口、或者交换涉及计数），这一轮"多余的自交换"就可能引入 bug。< 比 <= 更安全，因为它在结构上就排除了自交换。

6. 代码风格清晰

• 变量命名见名知意（left、right、tmp）。
• 用 const int 定义常量，避免"魔术数字"（Magic Number），改数组上限时只需改一处。
• 注释清晰划分了"输入"、“交换”、"输出"三个模块，可读性极强。

双指针的通用形态

逆序只是双指针最朴素的一种。它的本质是用两个不同移动策略的游标，把 O(n²) 的嵌套扫描压成 O(n) 的单趟扫描。常见变体：

形态	移动方式	典型场景
对撞指针	left++ / right–，相向而行	数组逆序、两数之和（有序）、回文判断、盛水容器
快慢指针	一个走一步，一个走两步	链表判环、找中点、找倒数第 k 个
同向双指针（滑动窗口）	右指针扩张，左指针收缩	最长无重复子串、最小覆盖子串、定长窗口最值
分离双指针	各自独立推进	归并两个有序数组、合并区间

它们的共同前提是：数据具有某种单调性或不变量，使得"某个指针不需要回头"。

深度思考：双指针为什么能省掉一层循环？它的合法性条件是什么？

关键在于单调性与不变量（invariant）：当某个条件一旦成立/不成立就不会再逆转时，指针可以单向移动而不必回溯，从而把"枚举所有 (i, j) 对"的 O(n²) 压缩为"每个指针各走一趟"的 O(n)。

以对撞指针为例：逆序交换中，left 和 right 的移动不依赖任何数据条件，纯按位置推进，所以合法性是显然的——它只是"把第 k 个和第 n-1-k 个换一下"这个数学定义的直接实现，交换 $\lfloor n/2\rfloor$ 次就完成。

真正需要论证的是带条件的双指针。比如"有序数组中找两数之和等于 target"：left 指向最小、right 指向最大，若 a[left] + a[right] < target 则 left++，若 > target 则 right--。为什么这样可以？因为数组有序——当 a[left] + a[right] < target 时，对当前 left 而言，任何 right' <= right 都只会让和更小，所以 left 这一列的所有组合都可以一次性排除。这就是"单调性允许剪枝"。

反之，如果数组无序，left++ 无法排除任何组合，双指针立刻失效——必须排序（O(n log n)）或改用哈希表。

不变量视角更形式化：维护一个"候选区间" $[left,right]$，每次移动都保证"最优解仍在区间内"。逆序问题的不变量是"区间外的元素已经就位"；两数之和的不变量是"若存在答案，必在 $[left,right]$ 中"。只要不变量成立，指针的单向移动就不会漏解。

特性	单指针 + 嵌套循环	双指针
访问次数	O(n²)，每个元素被反复访问	O(n)，每个元素最多被访问常数次
空间	O(1)	O(1)
合法性前提	无（暴力总能做）	需单调性 / 可剪枝性 / 不变量
典型失败场景	无	无序数据上强行用对撞指针

还有一个容易被忽略的工程点：双指针的"保护原变量"是它优于"消耗式循环"的根本原因。while(n>0) n-- 是破坏性遍历（destructive traversal），遍历完数据就没了；而双指针用独立的 left/right 游标，原数据完好无损。这在需要多次遍历、或需要回溯的场景下是决定性的——本质上，它是把"状态"从输入变量里剥离出来，交给专用的局部变量保管。这和 Day 2 讲的"作用域保护"、Day 4 讲的"状态变量必须清零"是同一个思想的三个侧面。

📖 结论：双指针的合法性来自单调性/不变量——一旦某方向的移动能排除整片候选，指针就无需回溯，从而将 O(n²) 降为 O(n)；其空间 O(1)、原数据无损，本质是用独立游标把遍历状态与输入数据解耦，与作用域保护、状态清零同属"隔离可变状态"这一原则。

---

📝 总结

Day 5 这四块内容，表面是"数论"“模拟”“DP”“数组操作”，内核都是同一句话：找出不必要的工作，然后删掉它。

四把刀，四种删除

刀法	删掉什么	代表	效果
生成代替判断	无效的筛选与试除	埃氏筛 i*i 起点、欧拉筛 break、开关灯 j += i	O(N²) → O(N log log N) → O(N)
不存代替全存	冗余的存储	杨辉三角滚动数组、组合数公式	O(n²) → O(n) → O(1)
游标代替消耗	重复的访问	双指针	每个元素访问 O(n) 次 → O(1) 次
顺序代替隔离	多余的空间	滚动数组逆序更新	双数组 → 单数组

几条硬结论

1. 试除法的 TLE 不是因为算法错，是因为重复太多——52.5 亿次运算里，绝大多数是在重复试除同一个因子。改成 k*k <= i，内层从 35 万次降到 591 次。
2. i*i 起点是埃氏筛的灵魂——i*i 之前的倍数一定被更小的质数筛过了，这是严格无损的优化，不是近似。
3. i*i 会溢出——int 上限 2.1×10⁹，而 350377² ≈ 1.23×10¹¹。写 1LL * i * i 或加守卫，否则是 UB。
4. 欧拉筛的 break 不是优化，是正确性条件——它保证每个合数只在最小质因子那一轮被标记，总标记次数 ≤ N，严格 O(N)。
5. 变量名必须和真实语义一致——is_prime[x] = true 表示"x 不是质数"这种写法，逻辑能过但调试会疯。改叫 not_prime。
6. j += i 比 j++ 加取模好，但要诚实——这题 n=5000，不优化也能过。真正的价值是建立"看到倍数就想步长"的条件反射，n=10⁶ 时它能救命。
7. 嵌套循环先问维度——时间依赖（有先后）放外层，空间并列（同时存在）放内层。分不清维度，就会写出一堆 if 揉在一起。
8. 滚动数组必须逆序——arr[j] = arr[j] + arr[j-1]，逆序时 j-1 还没被更新；正序时 j-1 已是新值，直接算错。
9. 逆序 vs 双数组，取决于依赖跨度——依赖只在相邻位置（杨辉三角）→ 逆序可救，省一个数组；依赖跨多方向（图像模糊 5 邻居）→ 顺序救不了，必须物理隔离。
10. 组合数先乘后除——val * (i-j) / (j+1) 有整除性保证；先除会截断。但中间乘积可能溢出，long long 是必须的。
11. 双指针省的不是循环，是"重复访问"——把每个元素被访问 O(n) 次压成 O(1) 次，前提是数据有单调性。
12. 保护输入变量——while(n>0) n-- 把 n 吃掉了，双指针用独立的 left/right 让原数据完好。

Day 1 管"值对不对"，Day 2 管"状态稳不稳"，Day 2.5 管"控制流收不收得住"，Day 3 管"栈谁在管"，Day 4 管"那些看不见的东西"，Day 5 管"哪些活其实不用干"。

刷到这儿我最大的感受是：从 O(n²) 到 O(n)，靠的从来不是更聪明的代码，而是发现"这件事其实做过一遍了"。 筛法是这个道理，步长法是这个道理，滚动数组和双指针也是这个道理。后面所有的算法优化，大概都是这个道理。

点个赞收藏一下呗～有理解不对的地方欢迎评论区指正

---

参考资料：

• 洛谷 B2085 第 n 个小的质数、B2082 开关灯、B2085 杨辉三角
• 《算法竞赛进阶指南》李煜东 —— 质数与约数、动态规划基础章节
• Mertens 第二定理：${\sum }_{p\le N}\frac{1}{p}\approx \ln \ln N+M$
• 欧拉线性筛（Linear Sieve）最小质因子唯一性证明
• CP-Algorithms: Sieve of Eratosthenes / Linear Sieve / Dynamic Programming

标签： C++ 算法竞赛 洛谷 素数筛 埃氏筛 欧拉筛 滚动数组 动态规划 双指针 时间复杂度 刷题笔记