做题时间长了以后我越来越确信一件事真正让人当场翻车的往往不是那些看半天都没思路的难题而是所有步骤都“看起来没问题”的简单题。AtCoder Beginner Contest 169 的 C 题 Multiplication 3就是一个摆在台面上的典型例子。题目一句话就能讲完给你一个小数 A一位小数和一个不超过 10^18 的整数 B输出 A×B 向下取整的结果。听着就是一行乘法和一次取整的事可偏偏有大量选手在某个测试点上连续吃 WA。这篇文章把这个题从坑到解完整拆一遍顺便把“浮点数精度”这个老生常谈的问题讲透适合刚接触竞赛题的新手也适合被精度题坑过但没深究原因的朋友。1. 一眼看懂题目却交了三份错误答案1.1 题目到底在算什么先明确题目结构。输入是两个数第一个是带一位小数的浮点数 A满足 0 ≤ A 10第二个是整数 B满足 0 ≤ B ≤ 10^18。要求输出 floor(A×B)也就是 A 乘 B 之后把小数部分直接丢掉只保留整数部分。举例来说A 2.5B 4那么 A×B 10.0输出 10A 1.1B 3那么 A×B 3.3向下取整输出 3。题目本身完全没有绕弯子的地方真正动手写代码之前谁都不会觉得这种题能有什么波澜。但这里有一个非常容易忽略的信号A 是一个小数。B 最大到 10^18A×B 的结果可能非常大同时取整操作又极其敏感。这两个条件叠加在一起就是精度问题最喜欢的温床。我见过不少人在赛后看别人的代码时恍然大悟才发现自己从头到尾想的都是浮点数而没有意识到这种“简单题”其实是在考你浮点数能否安全落地。1.2 直觉解法为什么挂在某个测试点上我第一次写这题时思路和大多数人一样C 代码大概长这样#include bits/stdc.h using namespace std; int main() { double a; long long b; cin a b; cout (long long)(a * b) endl; return 0; }本地跑样例输入 2.5 和 4输出 10正确输入 1.1 和 3输出 3也正确。自信提交前面几个测试点也是绿的然后某一次提交突然冒出一个 WA。那一刻人的第一反应通常是是不是哪里写成了四舍五入于是有人改成(long long)(a * b 0.5)还有人换成long double结果要么还是 WA要么只是把一个测试点的错误平移到了另一个测试点。为什么加 0.5 不行因为题目要的是向下取整不是四舍五入。向下取整是“不管小数部分是多少直接切掉”四舍五入是“小数部分超过 0.5 就进位”。两者在绝大多数数据上一致但在小数部分恰好落在 0.5 附近的数上会互相矛盾。比如真实结果是 3.6向下取整应该是 3但浮点结果如果是 3.59999999加上 0.5 再取整就变成 4题目期望的却是 3。这种修法等于拿一个错误的模型去掩盖另一个错误自然会越修越歪。1.3 翻车现象汇总赛后把 WA 的测试点数据拉出来看几乎所有翻车都指向同一个现象浮点数乘法算出来的值比你想象中的“正确答案”差了那么一丁点而且往往是偏小。偏小之后本应取整到 k 的结果被取整到了 k-1。比如某组数据期望输出 13double 算出来却是 12.999999999999998 这种数(long long)强制转换直接把它砍成 12。这不是某种编译器独有的 bug也不是某个语言写错了。它根植于二进制浮点数的表示方式任何用 double 或 float 直接做乘法的代码理论上都可能踩中。要理解这个题为什么这么设计就得先搞清楚浮点数在计算机里到底是怎么存的以及误差是从哪一步开始渗入的。2. 从二进制角度看浮点数的幻觉2.1 十进制小数与二进制小数不是一一对应我们平时写的小数都是十进制但计算机里的浮点数是用二进制存储的。二进制的每一位代表的是 1/2、1/4、1/8、1/16……这些分数之和。很遗憾十进制里很整齐的数字在二进制里可能是一个无限循环小数。最经典的例子是 0.1。0.1 转换到二进制得到的是 0.00011001100110011001100……其中“1100”会无限循环下去。但 double 类型只有 53 位二进制有效数字它没法装下这个无限序列只能截取前面有限的一段然后四舍五入近似。于是 0.1 在 double 里并非精确的 0.1而是一个很接近但略有偏差的值实际存下来大约是 0.1000000000000000055511151231257827021181583404541015625。你可以这样理解就像我们在十进制里用 0.333333 去近似 1/3平时计算看不出问题但只要做了很多步运算误差就会慢慢积累。十进制有这种“近似误差”二进制同样有。只不过二进制丢精度的场景更隐蔽因为它丢精度的地方恰好是十进制小数最熟悉的区域。2.2 输入一个数已经发生了一次近似当你写double a; cin a;读入 1.1 时读进去的并不是数学上精确的 1.1而是那个无限接近 1.1 的二进制近似值。这一步误差叫“表示误差”是浮点数精度问题的第一层来源。接下来做乘法时事情变得更复杂。两个二进制小数相乘结果通常也不是一个可精确表示的二进制小数于是计算机又要把乘积舍入到最近的 double 值。这第二层舍入误差会把第一层误差继续放大或缩小。也就是说你以为自己只做了一次运算实际上输入近似了一次乘法运算又近似了一次最终拿到的数字已经是“经过两轮加工”的产物。把这两个误差叠加起来最终结果有可能比真实值大一点也可能比真实值小一点。大一点的时候floor 或强制转换还能歪打正着得到正确答案小一点的时候如果真实值又恰好在整数边界上就必然出问题。第 1 章里提到的 12.999999999999998 就是这么来的真实乘积是 13浮点乘积却落在 13 的下方一点点。2.3 为什么这个题天然容易踩中这题最容易踩坑是因为它的判定方式不是“近似相等”而是“取整后精确相等”。取整操作对浮点误差极其敏感只差 1e-15就能把结果从 k 推到 k-1。而题目中 B 可以很大A 又是一位小数测试点设计者完全可以构造出大量“真实乘积恰好是整数”的边界数据专门等着那些直接用 double 硬算的程序翻车。这时候你会发现试图用更高精度的long double解决问题也只是把阈值往后推了一点点并不能根除风险。因为 long double 依然是浮点数依然存在表示误差只要测试点精心构造它同样可能落在整数边界下方。真正可靠的思路只有一个如果这个问题可以不用浮点数那就干脆彻底别碰浮点数。3. 正解把小数问题变成整数问题3.1 核心思想既然只有一位小数就让小数点消失A 有一位小数这意味着 A 可以精确写成整数 A10 除以 10。例如 1.1 就是 11 / 102.5 就是 25 / 109.9 就是 99 / 10。也就是说A10 round(A × 10) 是一个精确的、没有任何误差的整数。我们要求的 floor(A × B)完全可以改写成floor(A × B) floor(A10 × B / 10)这里 A10、B 都是整数整个式子从输入到输出全部在整数范围内进行。整数运算在计算机里是精确的不存在表示误差也不会产生舍入误差。这个思路用一句话概括就是把小数问题先放大成整数问题算完以后再缩小回来。很多涉及到浮点数精度的题目一旦想通这一步代码难度几乎瞬间归零。为什么要强调“字符串解析”而不用round(A * 10)因为后者依然要先把 A 读成浮点数等于又把表示误差请了回来。既然目标是绕开浮点那就要绕得彻底直接读字符串从字符层面把 A 的整数部分和小数部分抠出来。3.2 C 实现小心溢出这个隐藏 boss在 C 里我推荐这种写法#include bits/stdc.h using namespace std; int main() { string s; long long b; cin s b; // 把 1.1 这类字符串解析成整数 11 long long a10 0; for (char c : s) { if (c ! .) { a10 a10 * 10 (c - 0); } } // 分段计算避免 a10 * b 直接溢出 long long q a10 / 10; // A 的整数部分 long long r a10 % 10; // A 的小数那一位 long long ans q * b r * b / 10; cout ans \n; return 0; }这里最大的隐藏陷阱是溢出。A 最大接近 9.9所以 A10 最大是 99。B 最大是 10^18两者直接相乘是 99 × 10^18 9.9 × 10^19。这个数不仅超过 long long 的极限约 9.22 × 10^18连 unsigned long long约 1.84 × 10^19都装不下。所以在 C 里如果直接写long long prod a10 * b;还没等到输出前面的乘法就已经溢出成负数或乱值了。分段计算的巧妙之处在于它把一次危险的乘法拆成了两次安全的乘法。q 不超过 9所以 q × b 最大约 9 × 10^18在 long long 的边界内r 不超过 9所以 r × b / 10 最大约 9 × 10^17更加安全。两者相加得到最终答案整个过程没有一步溢出。如果你所在的比赛环境支持__int128也可以直接__int128 prod (__int128)a10 * b; long long ans (long long)(prod / 10);但要注意prod / 10本身可能超过 long long 范围所以输出时依然要小心分段法可以避免这个麻烦。我建议优先掌握分段写法因为它对类型范围的思考更扎实。3.3 Python 实现别对 float 用 int()Python 的整数没有位数上限不存在 C 那种溢出问题所以代码可以写得更短s, b input().split() b int(b) integer_part, frac_part s.split(.) a10 int(integer_part) * 10 int(frac_part) ans a10 * b // 10 print(ans)这段代码直接在字符串层面处理 A全程没有经过浮点数。//是整数除法正好实现向下取整。如果你在 Python 里偷懒写成这样就又会踩坑a float(input()) b int(input()) print(int(a * b))在本地某些数据上可能没问题但遇到float(8.7) * 10这类情况Python 可能给你 86.99999999999999int()再一截断结果变成 86。更麻烦的是int()是向零取整对于正数表现和向下取整一致看起来人畜无害实际上误差已经被它悄悄放大了。所以 Python 也不能放纵地用 float字符串解析或Decimal才是稳的。3.4 最后一步为什么必须是整数除法这个细节看似不起眼实际上很关键。在 Python 里可以写a10 * b // 10在 C 里可以写a10 * b / 10但前提是参与运算的必须是整数且除法是整数除法。如果 C 里把 a10 或 b 声明成 double那么a10 * b / 10就变成了浮点除法最终结果又回到二进制近似问题。曾经有个朋友把代码改成这样之后觉得“我已经放大过了应该没问题了吧”结果照样 WA。原因很简单放大之后又做了浮点除法等于二次引入误差前面的努力全部白费。整数除法的好处是它直接截断小数部分语义上恰好就是题目要求的向下取整。因为分子是精确整数分母是正整数 10所以a10 * b / 10的整数部分一定等于 floor(A × B)不多不少。4. 边界测试拆解把坑全部踩一遍4.1 构造一组典型边界样例题自己做完了最好再主动构造一批边界数据来验证。下面这些是我会用来测试的数据每一行都能对应一类潜在问题输入 A输入 B正确答案说明0.010000000000000000000A 最小的情况0.11000000000000000000100000000000000000一位小数乘大整数1.133最基本的非整结果1.31013真实结果是 13double 容易算成 12.999... 的典型数据2.5410二进制可精确表示的小数9.910000000000000000009900000000000000000结果超过 signed long long 范围第三行“1.3 和 10”就是那种会让 double 方案翻车的测试点期望输出 13浮点结果却有可能会是 12.999999999999998向下取整后输出 12。这类数据不是随机构造的而是专门瞄准了浮点数表示误差最痛的那条边界。4.2 用 Decimal 或 Fraction 做交叉验证如果你本地没有数据生成器可以用 Python 的Decimal写一个参考实现用来验证 C 或其它语言的整数解法是否正确from decimal import Decimal s, b input().split() b int(b) d Decimal(s) print(int(d * b))Decimal使用十进制表示不会遇到二进制小数的表示误差所以它可以作为“标准答案”来生成测试数据。我在本地会把这份脚本和相关题目的对拍器放在一起随机生成几千组数据把整数解法和 Decimal 结果逐一比对确认无误后再提交。这种对拍习惯比肉眼盯几组样例可靠得多。4.3 如果题目改成四舍五入怎么办把题目稍微改一下如果要求输出四舍五入后的整数部分整数解法依然有效只是最后一步要变一下。四舍五入到个位等价于先给分子加上 5再做整除round(A × B) (A10 × B 5) / 10因为A10 × B / 10的小数部分如果不小于 0.5也就是余数不小于 5加 5 之后就会进到整数部分如果小于 0.5加 5 也不会影响整除结果。这个技巧在其它题目里也经常出现比如要求保留一位小数或两位小数的输出都可以用类似的“先放大再修正最后缩小”思想。掌握这个思路之后很多浮点取整的题都能转化成纯整数问题。5. 同类精度陷阱的识别与规避5.1 哪些信号意味着你要警惕浮点数经历这题之后我总结出三个明显的危险信号只要同时命中两个以上我就会下意识地寻找整数解法。第一个信号是输入里有小数。只要输入出现小数就说明“表示误差”不可避免。第二个信号是要求输出整数尤其是向下取整、四舍五入、整除这一类操作它们对边界极其敏感。第三个信号是数字范围很大大到接近语言内置整数类型的上限这时溢出和精度问题会同时出现。举个例子如果一个题让你读入一个浮点数乘以某个整数后把小数部分去掉它几乎就是乘法精度题的翻版。看到这种题第一反应不是“用 double 直接算”而是“怎么把这个小数变成精确整数”。这种条件反射只能靠多做题养出来但一旦养成以后见到类似题就再也不会慌。5.2 不同语言里的替代方案怎么选处理精确小数不同语言有不同工具C 可以用字符串手动解析Python 可以用Decimal或FractionJava 有BigDecimal。但工具选型要考虑竞赛环境和题目规模。Decimal和BigDecimal的优点是直观、不容易出错缺点是慢、占用内存大。如果题目只做一次乘法它们完全够用但如果要循环几十万次高精度类型的性能劣势就会显现。Fraction类似适合做理论推导验证在大规模运算里要慎用。相比之下把小数放大成整数的思路没有任何额外开销也最容易保证正确性所以它一直是我在比赛中的首选。另一个细节是不要迷信long double或 Python 的float。它们确实比double精度高但仍然是二进制浮点近似数学上并没有根除误差来源。用高精度浮点去“碰运气”本质上还是在赌测试点没有戳中你的误差窗口这不是一个可靠的解题策略。5.3 我判断精度题的习惯清单最后分享一下我处理这类题的行动顺序。第一步看输入输出格式是不是“小数参与、整数产出”第二步如果是立刻考虑把小数部分转换成整数尽可能在字符串层完成解析第三步估算中间乘积是否会溢出如果会就用分段计算或者语言的任意精度整数类型第四步本地写一个基于Decimal或真分数的对拍脚本随机数据跑一遍确认解法没有遗漏边界。这套流程用熟了之后每次遇到乘法取整的题我基本都能在几分钟内拿出一个不依赖浮点数的稳定解法。至于这篇题解里的 Multiplication 3它本身并不难但它用最小的代价把一个非常重要、非常高频的竞赛知识点完整地暴露了出来值得任何一个想认真刷题的人停下来多看两眼。