← 目录 第 2 / 60 节 全部 60 节

02 · 循环、累加与整数溢出

把“算一次”升级成“算一百万次”：用 for/while 把重复劳动交给机器，用累加器收集结果，并在动手之前算清这个和会不会超过 2.1×10⁹。
⭐ 已学范围入门预计 50 分钟for/whilelong long溢出
本节出现的新函数 / 新语法（先看懂再用）

第 1 节的程序只做一次加法，这一节让它做一百万次。循环要想清楚三件事：从哪开始、什么时候停、每轮做什么；累加只想一件事：这个和最大能到多少。前者决定快不快（TLE），后者决定对不对（WA）。

先算最坏情况的上界，再写代码。

两个数先摆着：1+2+…+65536 = 2147516416，比 int 上限 2147483647 大 32769，存进 int 就是负数 -2147450880；而本节的例题要循环 183 万次。循环次数和数值范围是两件事。

新函数拆解 · for 循环
for (初始化; 条件; 步进) { 循环体 }
组成含义 / 格式要求
for两个分号隔出三段，分号不能省。
初始化进循环前执行一次，i 只在循环内有效。
条件每轮开始前检查。i <= n 配 i 从 1 起是 n 轮。
步进每轮末尾执行，这里 ++i 与 i++ 等价。
循环体只有一句也写花括号，以后加行不会错。
最小可运行示例
示例
long long sum = 0;
for (int i = 1; i <= 100; ++i) sum += i;        // 5050
for (int i = 0; i < 5; ++i) cout << i << " ";   // 0 1 2 3 4
注意

条件别写 i != n 配 i += 2：步进跨过 n 就永远退不出。

新函数拆解 · while 循环（含 break / continue）
while (条件) { 循环体 }
组成含义 / 格式要求
while每轮开始前检查条件，为真再转一圈。
何时用次数未知用它，次数已知（数 1..n）用 for。
改变量循环体里必须让条件最终变假，否则死循环 → TLE。
break跳出整个循环，适合“找到就停”。
continue跳过本轮剩余语句，for 会先做步进。
最小可运行示例
示例
double s = 0; int n = 0;
while (s <= 15) { ++n; s += 1.0 / n; }     // 退出时 n = 1835421
int x; while (cin >> x) { if (x < 0) break; cout << x << " "; }
注意

++n 和 s += 1.0 / n 换个顺序，答案就差 1。

新函数拆解 · 累加器（sum += x）
long long sum = 0; for (...) sum += x;
组成含义 / 格式要求
初值 0加法的单位元。局部变量不初始化是随机值。
类型要装得下最终结果：上界 = 项数 × 单项最大值。
计数器只加 1 的累加器，初值也是 0。
求积初值是 1，写成 0 结果永远为 0。
最小可运行示例
示例
long long sum = 0;
for (int i = 1; i <= n; ++i) sum += i;      // n = 1e9 时约 5×10^17
long long prod = 1;
for (int i = 1; i <= 20; ++i) prod *= i;    // 20! = 2432902008176640000
注意

求和 0、求积 1、求最小值 INT_MAX，都是让第一次运算不改变结果。

新函数拆解 · INT_MAX 与 LLONG_MAX
int INT_MAX; long long LLONG_MAX;
组成含义 / 格式要求
INT_MAX2147483647，求最小值的初值。
INT_MIN-2147483648，求最大值的初值。
LLONG_MAX9223372036854775807，19 位。
用法编译期常量，可直接输出。
只当边界别做运算：INT_MAX + 1 溢出成 INT_MIN。
最小可运行示例
示例
int mn = INT_MAX;
for (int i = 1; i <= n; ++i) { int x; cin >> x; if (x < mn) mn = x; }
cout << INT_MAX << " " << LLONG_MAX << "\n";   // 2147483647 9223372036854775807
注意

两个上限都是 2 的幂减一，末位一定是 7。记“19 位”比记数字实用。

新函数拆解 · printf 与 %lld
printf("%lld\n", 变量);
组成含义 / 格式要求
%lldlong long 的格式符，两个 l 表示 64 位。
%dint 的。给 long long 用只取低 32 位，输出垃圾。
%.2fdouble 保留两位小数。
\nprintf 不会自动换行。
别混用关掉 sync_with_stdio 后不要混用 printf 和 cout。
最小可运行示例
示例
long long s = 5000050000LL;
printf("%lld\n", s);        // 5000050000
printf("%d\n", (int)s);     // 705082704  ← 截断后的残值
注意

洛谷是 64 位 Linux，%d 读 long long 静默截断：不报错，只 WA。

五件东西拼起来，够做一道真题了。

例题 · 级数求和洛谷 P1035入门去洛谷做这题 ↗

已知 S_n = 1 + 1/2 + … + 1/n。n 足够大时，S_n 能超过任意给定的整数 k。

给定 k（1 ≤ k ≤ 15），求最小的 n，使 S_n > k。

输入格式：一行一个正整数 k。输出格式：一行一个正整数 n。

输入： 1 输出： 2
思路：部分和只能一项一项加

部分和没有公式，只能一次加一项：一个 double 累加器 + 一个次数未知的 while。

停的条件写 s <= k：还没超过就继续。题目要 S_n > k，等于 k 时还得再加一项。

先 ++n 再 s += 1.0 / n，让“加进去的项”和“当前的 n”始终对应；反过来写，输出得改成 n−1。

手算验证：k = 1 时 S_1 = 1 不够、S_2 = 1.5 够，答案 2；k = 2 时 S_3 ≈ 1.833、S_4 ≈ 2.083，答案 4。

完整代码
#include <bits/stdc++.h>
using namespace std;

int main() {
    int k;
    cin >> k;                  // 1 <= k <= 15

    double s = 0.0;            // 累加器：部分和，必须是浮点
    int n = 0;                 // 已经加了多少项

    while (s <= k) {           // 还没超过 k，就再补一项
        ++n;                   // 先定下“这一轮加第 n 项”，顺序不能反
        s += 1.0 / n;          // 写 1.0 才是浮点除法；写 1 / n 会永远停不下来
    }

    cout << n << "\n";         // 此时 s 第一次超过 k，n 就是最小解
    return 0;
}
逐行拆解
代码片段含义与理由
#include <bits/stdc++.h>万能头，顶掉 iostream、climits 等。
int k;1 ≤ k ≤ 15，int 足够。
double s = 0.0;累加器。0.0 表示“一项都没加”，也提醒这是浮点。
int n = 0;项数从 0 起步，进循环第一件事是把它变 1。
while (s <= k)s 没超过 k 就继续；退出时 n 恰是满足条件的最小值。
++n;先确定这一轮加第几项。放到下一行后面，最后 n 会多 1。
s += 1.0 / n;写 1.0 才触发浮点除法；写 1 / n 时 n ≥ 2 恒为 0，s 停在 1.0，循环退不出来 → TLE。
cout << n << "\n";输出项数并换行。
提交前先用三组数据自测

k = 1 → 2；k = 2 → 4；k = 15 → 1835421（真跑 183 万次循环）。

k = 15 只差 1，几乎一定是 ++n 与 s += ... 的顺序问题。

这道题的累加器是 double，不怕溢出。换成求和题，int 就会翻脸。判断只要一个乘法：项数 × 单项最大值，超过 2.1×10⁹ 就用 long long。

最坏情况上界类型
累加 10⁵ 个数，每个 ≤ 10⁹10¹⁴long long
累加 1..n，n = 655362147516416long long
累加 1..1005050int
两个 ≤ 10⁹ 的数相乘10¹⁸long long，且要先转
累乘 1..n，n = 136227020800long long
两处溢出的现场
int s = 0;
for (int i = 1; i <= 65536; ++i) s += i;
cout << s << "\n";             // -2147450880  ← 溢出成负数，编译器毫无提示

int a = 100000, b = 100000;
cout << a * b << "\n";         // 1410065408   ← 先按 32 位乘出残值
cout << 1LL * a * b << "\n";   // 10000000000  ← 1LL 把表达式抬成 64 位
乘法从左往右算：1LL * a * b 先让 a 变 64 位；写成 (long long)(a * b) 已经晚了。
这一节最容易犯的 5 个错（附症状）

累加器不初始化。long long s; 后直接 s += x，局部变量是随机值，小数据过、大数据 WA，且每次跑结果都不同。

用 1 / n 代替 1.0 / n：每项都是 0，累加器不涨，循环退不出 → TLE。

求和用 int：1+2+…+65536 得负数 → WA。项数 × 单项最大值 > 2.1×10⁹ 就换 long long。

long long ans = a * b; 两边都是 int，先溢出再赋值 → WA，要写 1LL * a * b。

边界差一次：i = 1; i < n 只有 n−1 轮 → 本节的题直接 WA。

自己动手复现

关掉页面，从空文件把 P1035 敲一遍，用 k = 1、2、15 三组自测，再提交。

改一改：把 double s = 0.0; 改成 int s = 0;，1.0 / n 改成 1 / n，跑 k = 1——程序不输出任何东西，它在死循环。Ctrl+C 打断，然后回答：n = 2 时 1 / 2 等于几？

再改一改：写 1+2+…+n，先用 int 输入 65536 看负数，再换 long long 看 2147516416。

数学补给 · 2³¹ − 1 与“这个循环要跑多久”

第一个数字是 2147483647。int 占 32 位：1 位符号 + 31 位数值，正数上限就是 2³¹ − 1，10 位数。所以十位以内基本装得下，十一位以上一定装不下。long long 用 63 位，上限 2⁶³ − 1，19 位。

第二个是调和级数 S_n = 1 + 1/2 + … + 1/n ≈ ln n + γ，γ ≈ 0.5772。反解 S_n = k 得 n ≈ e^(k−0.5772)：k = 15 时 n ≈ e^14.4228 ≈ 1.84×10⁶，正是答案 1835421。

kn ≈ e^(k−0.5772)循环次数
122
5838.3×10¹
10123671.2×10⁴
151.84×10⁶1.8×10⁶

两个推论。① 时间 = 循环次数 × 每轮工作量，每秒约 10⁸ 次简单操作，10⁶ 安全、10⁹ 危险。② 范围 = 项数 × 单项最大值，超过 2.1×10⁹ 就换 long long。写代码前把这两个乘法各做一遍，就是所谓的“条件反射”。

double 只有 15~16 位有效数字，超过 10¹⁶ 的整数存不准，精确的整数答案永远用 long long。本例敢用 double，是因为每加一项只涨 1/(n+1) ≈ 5.4×10⁻⁷，而总舍入误差只有 10⁻⁹ 量级。

举一反三 · 想清楚这些再往下走
  1. 累加模式能套在很多题型上：统计个数、求平均分、边读边比求最大值。各写一句核心语句，并说明累加器初值分别是多少。
  2. 把条件从 S_n > k 改成 S_n ≥ k，while 里怎么改？k = 1 时答案从 2 变成几？
  3. k 的上限放大到 100，按 S_n ≈ ln n + γ 估一下 n 有多大。这时“一项一项加”还现实吗？
  4. 求积的初值为什么必须是 1？算 1! + 2! + … + n! 并用 int 保存，n 最小取到几就出错？
  5. 把 while 改写成 for (n = 1; s <= k; ++n) s += 1.0 / n;，输出写 n 还是 n−1？差一从哪来？
自测：能全部回答再进下一节
挑战题 · 质因数分解
洛谷 P1075普及-去洛谷做这题 ↗

已知正整数 n 是两个不同质数的乘积，求较大的那个质数。

输入格式：一行一个整数 n（2 ≤ n ≤ 2×10⁹）。输出格式：一行一个整数，即较大的质因数。

样例：输入 21，输出 7（21 = 3 × 7）。

引导性提示（先只看这里）

别真去分解质因数：n 最大 2×10⁹，从 2 试到 n 要跑十亿次，必 TLE。

若 i 整除 n，则 i 与 n/i 成对出现，这一对里总有一个不超过 √n。

两个质数中较小的那个 ≤ √n。从 2 往上试，第一个命中的约数就是它。

想看思路了？点开完整思路

设 n = p × q，p < q 且都是质数。由 p < q 得 p × p < n，即 p < √n。

从 i = 2 递增，第一个满足 n % i == 0 的 i 必是 p：若 i 是合数，它必有更小的质因子，早就被找到了。

答案就是 n / p，输出后直接 return。循环写 i * i <= n，只需试到 √n ≈ 4.5×10⁴ 次。

还是不会？点开题解代码与拆解
参考代码
#include <bits/stdc++.h>
using namespace std;

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

    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {              // 从小到大，第一个约数就是较小的质因数
            cout << n / i << "\n";     // 另一个因子更大，正是答案
            return 0;                  // 找到即停
        }
    }
    return 0;
}
关键片段拆解
片段作用
long long n;n 最大 2×10⁹，int 装得下，用 long long 是为了后面的除法不贴边。
long long i = 2循环变量也取 64 位，否则 i * i 按 32 位算；数据到 10¹⁸ 就会溢出。
i * i <= n试到 √n 为止。写 i <= sqrt(n) 也行，但开方有浮点误差，乘法更可靠。
n % i == 0第一个命中的 i 就是较小的质数 p，n / i 就是较大的 q。
这题最容易错的地方
  • 循环条件写成 i <= n 或 i < n：对 n ≈ 2×10⁹ 要试十亿次，直接 TLE。
  • 想“先把质因数都存起来再比大小”：多写一遍试除，还可能把两个质数搞混。
  • 特判完全平方数：n 是两个不同质数之积，不可能是平方数，这行只会多一条错路。
延伸阅读 / 参考
← 01 输入输出与评测机制03 多重循环与图形输出 →