AtCoder ABC169 B题 Multiplication 2：大数乘法溢出判断的经典陷阱-北京尧图网络

AtCoder Beginner Contest 169 的 B 题 Multiplication 2是我印象里相当经典的一道“签到题里的陷阱题”。它表面上只是让你把 N 个整数乘起来如果乘积超过 10^18 就输出 -1若其中包含 0 则答案是 0。题目本身不长但第一次做的时候 WA 率出奇地高身边不少刷题老手也在边界条件上翻过车。如果你刚开始刷 AtCoder或者一直对大数溢出判断这个话题有点拿不准这篇文章可以帮你把这道题的套路彻底吃透以后遇到“乘到很大数”的问题都能条件反射地避开坑。1. 一个乘法题为何藏了这么多坑1.1 题意重述与数据范围先把题目说清楚。输入一个整数 N第二行给 N 个整数 A1, A2, ..., AN。你要做的就是用 64 位整数范围的逻辑去计算它们的乘积然后根据规则输出如果乘积超过了 10^18也就是 1000000000000000000输出 -1如果乘积等于或小于 10^18输出这个乘积如果这 N 个数里存在 0那么乘积就是 0当然也就不可能超过 10^18所以要输出 0。这个题的约束条件不复杂N 最大可以到 2×10^5每个 Ai 是 0 到 10^18 之间的整数。也就是说输入的每一个数本身就可能大得接近上限而一堆这么大的数乘起来中途超过 64 位整数的上限是非常容易的事。这道题属于 AtCoder Beginner Contest 的 B 题按理说难度定位应该是“稍微想一想就能过”。但实际提交的情况比想象中惨烈很多人不是不会写而是死在了细节上。做题这事有时候就是这样不是算法难而是出题人用最简单的包装把你平时忽略的边界问题全部暴露出来。1.2 出题人想考察什么表面上这题考的是“乘法”实际上考的是两个能力一个是数据类型边界的敏感度另一个是异常分支的处理顺序。先说数据类型敏感度。C 的 long long 能表示的最大值大约是 9.22×10^18而本题的阈值是 10^18看起来 long long 足够装下结果。但问题是计算的中间过程可能瞬间超出这个范围。比如 res 当前已经接近 10^18你再乘一个大于 10 的数结果直接溢出成负数或者变成一些奇怪的值程序就失控了。再说处理顺序。很多人的第一版代码是“把所有数乘起来最后判断是否超过 10^18”。这个思路在小学数学里合理但在计算机里不合理因为结果在乘的过程中就已经溢出丢失了最后拿去和 10^18 比较的是一个错误值。必须把判断放在乘法之前这就是这道题最核心的思维转变。所以这道题真正的价值不在于让你学会“乘两个数”而在于让你养成一种防御式编程习惯下手计算前先评估结果是否会越界遇到 0 这种特殊元素要先拦截而不是等它和数据一起参与完运算再补救。2. 两个必须提前解决的问题零与溢出2.1 零必须放在最前面处理先看 0 的问题。如果数组中存在 0那么最终乘积一定是 0这是数学上的铁律。不管其他数有多大哪怕是 10 个 10^18 相乘只要乘上一个 0整个结果就是 0。所以理论上只要检测到 0就可以直接输出 0连后面的乘法都不用做了。有人会问那我如果正常乘遇到 0 的时候 res 变成 0最后判断“res LIMIT”输出 0 不也行吗理论上行得通但这里面有个隐患。在你还没有碰到 0 之前乘积可能已经爆炸溢出了。举个例子如果序列是 [10^18, 10^18, 0]前两个数乘完已经超过 long long 的表示范围等到乘第三个 0 的时候程序操作的是个溢出后的垃圾值没法还原成合法的 0。所以标准做法是在读入数组后先单独循环一遍检查是否存在 0。只要发现有 0直接输出 0 并返回完全不进入乘积判断的主流程。这样做既安全又省时间因为这个检查是 O(N) 的对整个程序效率没有任何压力。还有一个小细节容易被忽略如果你用“res 0”来判断结果是否为零但 res 本身是因为之前乘了 0 才变成 0那没问题可如果 res 归零之前就已经溢出了这个判断就不可靠。所以正确的顺序一定是“先探测输入中有没有 0”而不是“依靠乘积结果来判断”。2.2 除法判溢出的原理等 0 的问题处理完剩下就是要考虑“怎么在乘法发生之前判断出它会超限”。这里用到的技巧非常经典比较大小关系时不直接乘而是把乘法转换成除法。假设当前乘积是 res下一个要乘的数是 x想判断 res * x 是否大于 LIMIT。因为两边都是正数这个判断可以等价地改写成如果 x LIMIT / res那么 res * x LIMIT。这里用整除也不会影响判断的准确性。因为 LIMIT / res 是向下取整只要 x 大于这个商说明 res * x 一定已经超过 LIMIT 了如果 x 小于等于这个商即使两者相乘也还在 LIMIT 之内可以放心乘。这个技巧的本质是把未来可能发生的溢出提前拦在门外。你根本不需要一个中间变量去装“res * x”这个可能爆炸的数只用一次除法就完成了风险评估。我在讲给新手听的时候喜欢用开车来类比你想知道这辆车能不能顺利通过前方限高架不需要真的以 120 码的速度冲过去撞一下再后悔你只需要看一眼高度数据提前在到达限高架之前做出判断。除法判断就是这样一把提前丈量的尺子它让程序不用亲身体验溢出就能知道前方是悬崖。2.3 为什么“乘完再判断”必死很多新手写出来这样的代码long long res 1; for (int i 0; i N; i) { res * A[i]; if (res LIMIT) { cout -1 endl; return 0; } }这代码的问题在于res * A[i] 这一句一旦乘积真的超过 long long 的范围后续的一切行为就是未定义的。在常见的 x86 编译环境下有符号整数溢出通常是环绕成负数但也有可能被编译器优化成完全不可预期的行为。更关键的是一旦溢出发生res 变成一个负值你的“res LIMIT”判断就再也无法正确触发了程序会输出一个莫名其妙的负数给评测系统最后得到一个 WA。所以结论很清晰判断必须发生在乘法操作之前。简而言之你判断的是“即将要进行的乘法是否会溢出”而不是“刚才进行的乘法是否溢出了”。前者是先见之明后者是事后诸葛而且这个事后还无法补救。3. 可以直接抄作业的AC代码与逐行解释3.1 C17 完整代码给出我常用的 AC 写法使用 C17 标准提交没有问题#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorll A(N); for (int i 0; i N; i) { cin A[i]; } const ll LIMIT 1000000000000000000LL; for (int i 0; i N; i) { if (A[i] 0) { cout 0 \n; return 0; } } ll res 1; for (int i 0; i N; i) { if (res LIMIT / A[i]) { cout -1 \n; return 0; } res * A[i]; } cout res \n; return 0; }这套代码很短但每一步都踩在了正确的逻辑上。3.2 逐段解读与细节说明先看编译预处理和头文件bits/stdc.h是竞赛里很常用的万能头在 AtCoder 的环境下编译没有问题。ios::sync_with_stdio(false); cin.tie(nullptr);这两行是经典的 C 输入输出加速数据量大的时候能明显减少耗时属于竞赛选手的习惯动作。读入 N 和数组 A 之后第一件事是扫描数组中有没有 0。这里我用的是普通 for 循环如果发现某个元素是 0直接输出 0 并结束程序。为什么要单独写这个循环因为 0 的存在会直接改变整个问题的答案且这个答案不会被任何溢出干扰所以必须提前拦截。接下来定义 LIMIT 为 10^18。注意这里的写法1000000000000000000LL结尾的 LL 表示把这个字面量当作 long long 类型避免某些编译环境把无后缀的整数常量当成 int 处理。10^18 这个数远远超过 int 能表示的范围不加后缀在某些场景下会报警告甚至导致意外行为。然后进入主循环。循环里先判断res LIMIT / A[i]这个条件等价于判断res * A[i] LIMIT。如果成立直接输出 -1 返回。如果不成立才执行res * A[i]。这里有个细节值得注意因为我们已经提前检查过数组里没有 0所以循环里所有 A[i] 都是正数不需要担心除零问题。而且 res 在每一轮乘法后都不会超过 LIMIT所以 LIMIT / A[i] 这个除法是安全的。3.3 测试样例与边界值验证光说思路不够我拿几个典型输入验证一下。样例一3 1000000000 1000000000 1000000000三个 10^9 相乘结果是 10^27远超 10^18程序会在第二轮或者第三轮触发超限判断并输出 -1正确。样例二2 0 1000000000000000000数组里有 0直接输出 0。这里如果不提前处理 0先乘 0 得到 res0再乘 10^18理论上也能得到 0但为了代码的确定性还是提前拦截最稳。样例三1 1000000000000000000单个数是 10^18乘积恰好等于 LIMIT。题目说“超过 10^18”才输出 -1等于的情况应该输出原值。我们的判断条件是res LIMIT / A[i]因为 1 1 为 false所以不会输出 -1最终输出 10^18。这个边界非常容易写错很多人写成就会把恰好等于 LIMIT 的情况误判为 -1丢掉一个 AC。4. 高频WA原因与排查实录4.1 错误思路盘点我周围的人第一次提交这道题最常见的三版错误代码大概是这样的。第一版完全没有判断溢出直接累乘到最后输出甚至没有比较 LIMIT。这种代码连规则都没仔细看自然 WA 得毫无悬念。第二版先乘后判断如下res * A[i]; if (res LIMIT) { ... }我前面说过一旦溢出发生res 变成负数这个判断就形同虚设。这种写法的错误率极高而且难以在本地小数据中复现因为小数据根本不会溢出。第三版判断条件写成了 LIMIT把恰好等于 10^18 的情况也当成超限处理。这种问题在样例数据里不容易暴露因为样例很少给出恰好等于边界的值但一旦评测数据里出现“单个数为 10^18”或者“乘积恰好为 10^18”的输入就直接 WA。4.2 本地测试与在线判定的环境差异还有一个经常让人头疼的问题是代码在本地跑得好好的交上去却 WA。这种情况多半是数据类型或者编译器行为导致的差异。本地开发环境可能是 64 位系统int 是 4 字节、long long 是 8 字节这没问题。但如果你用了 int 去存中间乘积int 的最大值是 2.1×10^9 左右随便两个大点儿的数相乘就爆了而你的本地编译器可能不会报错只是默默得到错误结果。所以这类题目第一步就要确认所有参与乘法的变量都是 long long。另一个差异在于有符号整数溢出的表现。C 标准里有符号整数溢出是未定义行为也就是说编译器可以按任何方式处理。本地没有开优化时可能你观察到的现象是溢出后取模回绕但 AtCoder 的评测机开了 O2 优化后情况可能会更复杂。不要试图依赖这种未定义行为最稳妥的办法就是提前用除法判断根本不触发溢出。4.3 我的调试心得作为一个被边界条件折磨过很多次的人我后来给自己定了一条规矩所有涉及乘法、加法、快速幂这类运算的题目先画一遍数据范围找出这个类型能表示的最大值再给每个变量做一次“会不会溢出”的推演。遇到这道题我在本地测试时会格外追加一组边界用例N1A[0]10^18N1A[0]10^181N2A[0]10^9A[1]10^9N2A[0]0A[1]10^18。这四组数据分别覆盖了恰好等于上限、刚好超限、乘法越界、零的特殊情况跑一遍基本能把代码中的所有逻辑分支验证完整。调试过程中有个技巧值得分享如果你不确定某个条件在边界处是否成立就用数字代入手算一遍。例如判断res LIMIT / A[i]时如果 res 是 1A[i] 是 10^18那么右边 LIMIT/A[i] 是 11 1 为 false所以合法。如果 A[i] 是 10^181右边 LIMIT/A[i] 就是 01 0 为 true所以非法输出 -1。逻辑非常干净几乎不存在歧义。5. 同类坑题的变体与思维沉淀5.1 大数乘法出现在 LCM 问题里这道题处理乘积溢出的手法在后续刷题中会频繁复用。最典型的是求多个数的最小公倍数LCM这个问题的难点不只是算法本身还有计算过程中 lcm(a, b) a / gcd(a, b) * b 这一长串乘法的溢出风险。如果你直接写a * b / gcd(a, b)当 a 和 b 都很大时a * b 会先溢出结果就错了。正确写法应该是先除后乘a / gcd(a, b) * b这样能让中间结果保持在更小的范围内。这本质上还是“调整运算顺序避免中间量爆炸”的思路和这道题的除法判断殊途同归。我印象里不少涉及 LCM 的题目AC 率低不是因为选手不会求公约数而是因为这一步乘法溢出。从 Multiplication 2 里把“先除后乘”和“乘前判断”这两个习惯带上后面会少踩很多坑。5.2 二分答案和 DP 里的乘法溢出乘法溢出不仅在数学题里出现二分答案里也经常暗藏杀机。比如在判定一个数 mid 的平方是否超过某个上限时很多人直接写mid * mid Kmid 稍大一点mid * mid 就可能超出 long long 范围。正确做法是把判断改写成mid K / mid或者用 long double 过渡一下再用浮点比较。再比如动态规划里更新最大值时如果状态转移涉及乘法也要随时想着会不会爆。竞赛中一个常见的经验是只要题目给出的数据范围上限是 10^5、10^9 甚至 10^18你在设计状态和计算过程时就必须把每个中间结果的最大可能值估算一遍而不是想当然地认为最终答案不超范围就没问题。中间步骤的溢出往往比最终结果溢出更隐蔽。5.3 “先判后用”的通用套路做多了这类题之后你会提炼出一个通用套路在对某个变量执行可能触发溢出的运算之前先构造一个安全的等价判断如果判断不通过就直接走异常分支绝不让那一步真正执行。这个套路可以应用在很多场景里乘法之前用除法判断结果是否会超限加法之前用减法判断是否会超过类型的最大值快速幂里每次乘法前检查 base 和 pow 是否会让当前结果超出目标范围数组下标加法前先检查是否越界。与其说这道题教你乘法不如说它教你一种程序员的基本素养对即将发生的运算保持警惕对数据边界保持敏感。这种素养不是看几篇题解就能形成的而是在一道道 WA 里积累出来的。我之前在这类题上翻过很多次车后来每次看到“乘积”“大数”“不超过某个上限”这些关键词第一反应就是画数据范围、找边界条件、设计提前判定这顿操作已经变成了肌肉记忆。如果你刚接触 AtCoder建议把这道题的代码收藏起来过一周再不看任何题解手写一遍。什么时候你能一口气写出“先判零、再除判、最后乘”三段式结构这道题就算真正吃透了。

AtCoder ABC169 B题 Multiplication 2：大数乘法溢出判断的经典陷阱

相关推荐

以文搜图和以图搜图，为什么不能共用一个库

软考高项备考捷径：用编书人思维高效通关三科

LoRA 的秩取 8 还是 64：先把参数账算清

更多资讯

MySQL单表查询详解：语法、过滤、分组与分页优化

Spring框架演进与核心设计深度解析

回收商过磅少了两百公斤说“地磅就这样“，月底结账又压价？企业微信聊天记录导出留痕攻略

UOS系统部署Nginx Web服务器的原生适配指南

Hive数据导入HBase的BulkLoad方案：MapReduce与Spark实现全解析

随机化快排实战：防退化、稳性能、抗恶意输入

今日更新

小波包能量谱原理与MATLAB实现：从频带分解到故障特征提取

基于LSTM的网易云音乐评论情感分析：数据清洗与模型调优实战

Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？