乘法溢出预判与边界处理：AtCoder ABC169 B题深度解析

最近在带一个学弟刷 AtCoder Beginner Contest 的套题，发现很多新手在 B 题这种看似简单的乘法题上栽跟头。虽然 B 题定位是“轻松签到”，但一旦涉及大数边界和溢出判断，AC 率其实并没有想象中那么高。正好借AtCoder Beginner Contest 169 的 B - Multiplication 2这道题，把这类“乘起来会爆掉”的题目一次性讲透，顺便聊聊这类题目背后的出题套路和解题思维。

先说结论：这道题的核心不是“会不会乘法”，而是“如何在乘法溢出之前提前知道它会溢出”，以及“怎么处理 0 这个特例”。很多人在本地测试时发现结果对，一提交就 WA，原因基本都是忽略了 0 乘任何数都是 0 的极端情况，或者用了超出语言限制的笨办法。下面我把从题意分析到最终 AC 的完整过程拆开讲，每一步会解释为什么这么做，而不只是告诉你“该这么做”。

1. 题目到底在考什么

1.1 题干完整解读

题目原文其实非常简短：给定 N 个整数 A1, A2, ..., AN，求它们的乘积。如果乘积超过 10^18，则输出 -1。

但这里面有个非常关键的前提条件：输入的所有数字，本身都不会超过 10^18。也就是说，单个数字不超限，但乘起来超限。这其实是在模拟现实场景中的“中间结果溢出”问题。如果你用 C++ 的long long去直接乘，一旦中间结果超过 9.22×10^18（long long 的最大值），立刻就会发生有符号整数溢出，变成未定义行为——这和你数学上算出来的答案可能是两码事。

为什么上限偏偏选 10^18 而不是 long long 能存的最大值？因为 10^18 是一个“安全阈值”，它比 long long 上限小大约 9.2 倍，留出了缓冲空间。判断的时候，如果乘积已经大于1e18 / a[i]，再乘a[i]就必定超限。这个“除法前置判断法”是规避溢出的核心手段，后面详细展开。

1.2 这道题的三个隐含考点

从出题者的角度，这道题并不是单纯考“求乘积”，而是通过一个简单的场景包装了三个隐含考点：

1. 溢出检测的时机：你必须在乘法发生之前判断它是否会导致溢出，而不是乘完了再后悔。
2. 0 的优先级最高：因为 0 乘任何数都等于 0，所以只要输入的 N 个数里存在一个 0，最终答案必然是 0，更不会超过 10^18。这个判断必须在逐项相乘之前完成。
3. 输入顺序和乘积顺序无关，但判断顺序有关：如果你先判断 0 再判断溢出，代码逻辑会更加清晰；如果混在一起，很容易出现逻辑漏洞。

很多新手第一个版本会写成“先乘完所有数，最后再判断是否大于 1e18”，这在数据量小、乘积不爆的时候当然没问题，但一旦乘积超过 long long 范围，程序已经开始 UB（未定义行为），后面所有判断都失去了意义。

2. 常见错误思路的踩坑实录

先把我见过的几种错误版本摆出来，这些错误非常典型，新手基本都踩过其中一个。

2.1 错误做法一：先乘后判

这是我见过最朴素的错误思路，代码长这样：

#include <iostream> using namespace std; int main() { int n; cin >> n; long long ans = 1; for (int i = 0; i < n; i++) { long long x; cin >> x; ans *= x; } if (ans > 1000000000000000000LL) cout << -1 << endl; else cout << ans << endl; return 0; }

这个写法的致命点在于：当ans已经超过 long long 上限时，ans *= x这一句发生了有符号整数溢出，结果是未定义的。在多数编译器上，它会产生一个奇怪的负数或者绕回的小正数，然后你后面的if (ans > 1e18)判断可能为 false，于是输出了一个错误的“成功答案”。这类问题在本地测试小数据时根本测不出来，因为小数据不会溢出。

为什么有人会这么写还过了几个样例？因为 AtCoder 给的样例往往没有构造那种“前 N-1 项乘起来刚好超限、最后一项不大不小”的边界数据，所以这种未定义行为未必会在样例中暴露，但提交上去就是 WA 或者 RE。

2.2 错误做法二：用浮点数判断

还有人图省事，用double来暂存乘积：

double ans = 1; for (int i = 0; i < n; i++) { ans *= a[i]; } if (ans > 1e18) cout << -1 << endl;

这个做法在数据小时看似没问题，但浮点数在 1e18 这个量级上，精度已经不足以区分整数差异了。比如ans * a[i]实际计算时可能因为舍入误差偏离了真实值。更直观地说：double的尾数部分在 1e18 量级下精度只到大约几百甚至几千，你无法可靠判断乘积是否恰好略大于或略小于 1e18。而且，乘法本身还有可能产生inf，导致判断结果完全失控。

2.3 错误做法三：到处用大数库或字符串乘法

在 C++ 里用__int128算是一个可行方案，因为它的上限大约是 1.7×10^38，容纳 10^18 的乘积绰绰有余，但如果你过度依赖它，会忽略核心考点。在 Python 里直接用内置的大整数不限制位数，算完再判断，这种方式反而没有练习到溢出判断的思维。这里不是反对你这么做，而是建议理解底层的判断逻辑。

再说一下 Python，在 Python 里整型是任意精度的，所以理论上你可以先乘后判而不会出错。但 AtCoder 的 B 题并不单纯考察 Python 语法，而是希望你在任何语言里都体现出对边界条件的敏感度。而且，Python 大整数乘以 10^18 量级的大数时，虽然不会溢出，但速度会更慢。在大 N 的场景下，虽然这道题 N 最大 10^5，Python 直接乘其实也能过，但我见过不少同学在这种简单题上用 Python 反而因为逻辑不严谨而 WA 的。

3. 正解思路与核心判断逻辑

3.1 为什么必须先判断零

如果输入序列中存在 0，那么最终乘积是 0，而 0 显然不超过 10^18，所以输出 0。这个逻辑一旦成立，后面所有乘法都不用做了。先判断零的原因有两层：

第一层：从数学语义上，0 是乘法的“零元”，无论前面乘出来多大，碰到 0 直接归零。 第二层：从工程实现上，如果不先处理 0，在逐项乘的过程中，一旦在此之前已经出现超过 1e18 的值，程序可能会提前退出（输出 -1），但你其实应该输出 0。因为你不能因为前面的数字乘起来太大就忽略后面还有一个 0 可以把一切都归零的事实。

比如输入是2 1000000000000000000 1000000000000000000 0，如果不在最开始判断 0，当乘到第二个 1e18 时就会判定“超过限额”而输出 -1，但实际上因为有 0，最终答案是 0。这就是零优先级最高的原因。

3.2 除法前置判断法的原理

在 C++ 中，假设ans是已经安全乘好的当前乘积，现在要乘一个新的数字x。我们想知道ans * x是否超过 1e18。你当然可以写成：

if (ans > 1000000000000000000LL / x) { cout << -1 << endl; return 0; }

为什么会这样判断？因为ans * x > 1e18等价于ans > 1e18 / x（在 x > 0 时成立）。而1e18 / x这个值是一个不超过 1e18 的数，用 long long 可以安全存储。再拿ans去和这个安全范围内的数比较，完全没有溢出风险。

这里有一个小细节：x 可能等于 0，但我们已经提前排除了 0，所以 x 一定大于 0，除法是安全的，不会出现除以零的情况。这一步逻辑顺下来非常丝滑。

3.3 完整 AC 代码（C++ 版）

#include <iostream> using namespace std; int main() { int n; cin >> n; long long a[100005]; bool has_zero = false; for (int i = 0; i < n; i++) { cin >> a[i]; if (a[i] == 0) has_zero = true; } if (has_zero) { cout << 0 << endl; return 0; } long long lim = 1000000000000000000LL; long long ans = 1; for (int i = 0; i < n; i++) { // 判断 ans * a[i] 是否超过 lim if (ans > lim / a[i]) { cout << -1 << endl; return 0; } ans *= a[i]; } cout << ans << endl; return 0; }

这套代码在 AtCoder 的评测环境下可以稳定 AC。注意这里我把所有数字先读进数组，是为了先统一检查一遍是否存在 0。你也可以在读入的过程中就记录has_zero，但必须在乘法开始之前完成对零的扫描，顺序不能乱。

3.4 为什么不在乘法过程中检查零

有些同学会写出下面的逻辑：先读入数，边读边乘，并且乘之前判断是否超限；如果某个时刻超限了就先标记“可能溢出”，等全部读完后再看有没有零。这个思路理论上可行，但代码反而更复杂了。因为你不但要维护一个“溢出标记”，还要在最终判断时区分三种情况：正常答案、溢出、有零。相比之下，先扫一遍零，再进入乘法循环，逻辑线清晰明了，也不容易隐藏 bug。

在实际比赛中，你需要的是在最短时间内写出最稳妥的代码，不是为了炫技。先扫零复杂度是 O(N)，与乘法的 O(N) 是同一个量级，但代码可读性和维护性高一个档次。

4. 通用的边界条件工具箱

4.1 当输入数字本身可能就是 0 或 1

0 的情况上面已经详细讲过了。这里补充说一下 1。如果 x == 1，那么lim / x就是 lim，所以当前 ans 只要不大于 lim 就安全，相当于“乘以 1 不会改变值”。这个分支不需要特殊处理，但如果你用乘法判定的思路，脑子里要有这个意识。

另外，0 的判定不能只寄希望于“输入数据没有 0”，AtCoder 的数据构造往往会包含 corner case，也就是偏要让你处理这种情况。所以无论你有多着急，必须显式处理 0。

4.2 乘积恰好等于 10^18 算不算超限

根据原题要求，超过 10^18 才输出 -1，等于 10^18 应该输出正常结果。所以判断条件里要用>而不是>=。对应到除法前置判断中，就是当ans > lim / x时认为会超限；如果ans == lim / x，说明乘起来刚好等于 lim，是合法结果。这个不仔细看就容易写错。

举个例子：lim / 2 = 500000000000000000，如果当前 ans 正好是 500000000000000000，而下一个数字是 2，那么 ans * 2 = 1e18，这是合法结果。如果你错用了>=判断，就会把它误判为超限，造成 WA。

4.3 乘积如何进行“预检”的直觉解释

假设你现在手里有一杯水，容量是 1e18 毫升，你每次要倒入一瓶量为 x 毫升的水。你怎么知道会不会溢出来？你不会真的等到水溢出来那一刻才判断（因为那样已经晚了，溢出不可逆），而是在倒之前看一眼：如果当前水量 > 杯子容量 / 这瓶水的容量，那倒进去肯定溢出来。这就是除法前置判断的日常类比。

如果你一下子往里倒很多瓶水，而倒之前不计算水量，你会发现水已经流了一地（溢出发生），这时候无论你怎么擦，程序状态都已经错了。所以分步判断是不可或缺的。

5. 语言差异与实现细节对比

5.1 Python 版本看起来更简单，但思维不能懒

因为 Python 整数没有固定上限，直接乘不会溢出，所以很多 Python 选手会写出下面这个版本：

n = int(input()) a = list(map(int, input().split())) ans = 1 for x in a: ans *= x if ans > 10**18: print(-1) else: print(ans)

这个代码确实是 AC 的，但前提是题目保证输入数量和单个数大小都在可接受范围。但问题是：如果某次乘积已经超过 10^18，后面又遇到 0，按你的代码逻辑ans被重置为 0，最终输出 0，其实也对。因为 Python 大整数可以表示中间结果，所以“先乘后判”在 Python 中结果是正确的。这相当于 Python 帮你在底层做了“大数溢出保护”，你在思维上反而体会不到这道题真正的考点。

但从训练思维的角度，我还是建议在 Python 里也写成“先判零再逐项判断是否超限”的流程，至少把这种边界处理逻辑留在大脑里，而不是完全依赖语言特性。

5.2 Java 的 long 也有相同问题

Java 的long和 C++ 的long long上限一致（都是 9.22×10^18），所以判断方式和 C++ 完全一样，用ans > LIMIT / x即可。区别只是语法上要写1000000000000000000L表示 long 字面量。这里不再重复贴码，思路一致。

5.3 C++ 中的 long long 技巧补充

在 C++ 中，有人喜欢用__int128来兜底，写法是：

__int128 prod = (__int128)ans * x; if (prod > 1000000000000000000LL) { ... }

这个当然也可以，但有两个注意点：第一，输出__int128时不直接支持流输出，得自己写转换逻辑。第二，如果题目数据量很大、N 很大，每次乘法都强转__int128，性能不会成为瓶颈，但代码里混用两种判断方式容易让人混淆。我个人建议还是用除法前置判断，既简洁又通用。

6. 从这道题延伸出去：乘积类题目的公共陷阱

6.1 不仅仅是判断溢出，还要判断时间复杂度

这道题的 N 最大是 10^5，O(N) 的算法是可行的。但如果 N 更大，比如 10^7，你就要考虑在读取阶段的同时完成判断，而不能先把所有数存进数组再扫一遍。好在 AtCoder 的 B 题一般不会上这么极端的 N，但如果你养成“读入即判断”的习惯，对后续写更复杂题是很有帮助的。

根据这道题的限制，边读边判的代码可以写成这样：

long long ans = 1; bool over = false; for (int i = 0; i < n; i++) { long long x; cin >> x; if (over) continue; if (x == 0) { cout << 0 << endl; return 0; } if (ans > lim / x) { over = true; cout << -1 << endl; return 0; } ans *= x; } cout << ans << endl;

但这里有个细节：如果先遇到的数字里没有零，但后面出现了零，零又要优先于“溢出标志”。所以严格地说，先扫零在逻辑上更直接。边读边判的话，你要先读入全部数据再判断，或者足够小心地处理“先出现溢出标记但后续有零”的情况。还是那句话，比赛不是炫技，选最稳妥的方式。

6.2 与后缀表达式、连乘求模的横向比较

还有一种常见题型是“求所有数的乘积对某个质数取模”。这种题就是另一个套路了，你必须在每一步乘法后取模，把中间值控制在模数范围内。但和本题的区别在于：取模题里“0”并没有优先级，因为你关心的是模意义下的值；而本题关心的是真实值是否超过上限。两种边界逻辑不能混用。

再比如某些题目要你判断“连乘得到的数的位数”，那就得取对数累加，和溢出判断又是不同的数学模型了。所以积累“乘法的边界处理”要结合具体场景，不要死记硬背。

6.3 现实工程中的溢出预判

如果你觉得 AtCoder 只是考试题，那可以想想现实中的场景：比如你在做一个购物车结算系统，单价和数量都是整数，总价字段是 64 位整数，你怎么防止用户在购物车里塞了足够多的商品导致总价溢出？你不可能等溢出发生后再报错，因为整数溢出后的订单金额可能变成负数，用户能直接“负支付”。

所以，在写入总价字段之前，预先判断“单价 > 总价上限 / 数量”几乎是唯一可靠的方法。这与本题的除法前置判断逻辑一模一样。理解这一点，你学到的就不只是一道 B 题的解法，而是一套通用的整数溢出防御策略，未来无论是写算法还是做业务系统，都会用到。

7. 整理一下完整解题流程和代码模板

如果你以后再遇到“求乘积但可能爆上限”的题，直接按下面的流程走，基本不会出错：

1. 读入所有数字，同时标记是否存在 0。
2. 如果存在 0，直接输出 0 并结束。
3. 将 ans 初始化为 1。
4. 遍历每个非零数字 x，判断ans > LIMIT / x：
   • 如果成立，说明后续乘积必超限，输出 -1 并结束。
   • 如果不成立，则安全执行ans *= x。
5. 遍历完所有数字后，输出 ans。

这个流程不仅适用于 10^18 上限，换成任意 LIMIT 都成立。你只需要修改 LIMIT 常量和判断条件，其他逻辑纹丝不动。

为了方便收藏，我把这个模板按 C++ 格式整理如下：

#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<long long> a(n); bool has_zero = false; for (int i = 0; i < n; i++) { cin >> a[i]; if (a[i] == 0) has_zero = true; } if (has_zero) { cout << 0 << endl; return 0; } const long long LIMIT = 1000000000000000000LL; long long ans = 1; for (int i = 0; i < n; i++) { if (ans > LIMIT / a[i]) { cout << -1 << endl; return 0; } ans *= a[i]; } cout << ans << endl; return 0; }

这里vector是可选的，如果不想用动态数组，普通数组也完全可以。但注意数组大小要开到 N 的上限加一点余量，AtCoder 的 N 上限是 10^5，所以long long a[100005]足够。

8. 常见问题速查表与排查方法

如果你在本地测试时用了一些“网上找的边界数据”，但结果依然对，却反复 WA，还有一个排查技巧：把long long换成__int128跑一遍同样的数据，对比结果是否一致。如果两种方式结果不同，说明你的 long long 版本已经发生了溢出，问题就出在那里。

9. 现场实录与补充经验

最后再说点题外话。我最初刷这道题时的实验室环境用的是老旧的 GCC 版本，那次我把-O2优化开起来之后，ans *= x在溢出时的行为变得特别奇怪——优化后的代码和不开优化的代码跑出的结果不一样。这让我意识到，凡是依赖“溢出后的自然回绕”来碰运气的代码，都是定时炸弹。

后来我给学生讲这道题，会先让他们在白板上写一遍“先乘后判”的错误代码，把结果跑给他们看——大数据样例下输出一个负数——然后他们自然理解为什么要提前判断了。这种印象比单纯背模板深刻得多。

另外，在 AtCoder 这类比赛中，看起来简单的 B 题往往审核的就是选手对边界条件的敏感度。很多排名靠前的选手并不是因为他们知道多少高深算法，而是他们能稳定地避开这些隐蔽的坑。如果你能把这种“预判溢出”的思维固定下来，将来遇到 AGC 或 ARC 里那些更复杂的“乘积类计数题”，你也会比别人少踩很多坑。

我个人在实际操作中的体会是，这道题的价值不在于它的难度，而在于它用最小的代码量，强迫你建立“在状态变坏之前阻止它”的思维习惯。无论你以后写算法还是做工程项目，这种提前预判的意识都会反复用到。希望这篇拆解能让你彻底看穿这个“简单 B 题”背后的门道，下次遇到类似问题不再靠试错通关。