《信息奥赛一本通》的 1082 题“求小数的某一位”我印象太深了。这题看着贼简单——不就是输出 a 除以 b 的小数点后第 n 位吗可当年我好几个同学都卡在这儿交上去不是答案错就是运行越界还有人对着屏幕怀疑人生明明 double 算出来就是那个数怎么提交就挂了。今天把这道题从头到尾拆开讲透顺便聊聊信息学奥赛刷题时最容易被忽视的“基本功”。适合正在刷一本通、准备入门信奥联赛、或者对“高精度计算”这三个字有点好奇的同学。1. 这题到底在考什么先别急着写除法1.1 题目表象下的三个隐藏坑先看题目描述信息奥赛一本通 1082 的原题要求是给定三个正整数 a、b、n求 a 除以 b 的小数点后第 n 位的数字。很多同学的第一反应是这有什么难的// 看完题就写的写法大概率会挂 double ans 1.0 * a / b; long long pos 1; while (pos n) { ans * 10; pos; } printf(%lld\n, (long long)ans % 10);这个写法坑在哪第一个问题是浮点数精度有限。double 类型大约只能精确表示 15 到 16 位有效数字而 n 只要稍微大一点比如 n 20小数点后第 20 位早就被浮点误差吞掉了你乘来乘去最后得到的是一个“看起来差不多但实际已经错到离谱”的数。第二个问题是溢出。你以为把 ans * 10 循环 n 次没什么但如果 n 是 100 万呢double 会变成 inf即便你用 long double也扛不住指数级的增长。更致命的是当你把 double 强转成 long long 的那一刻那个数早就超出 long long 的范围了转换结果完全不可预测。第三个问题是速度。就算你避开浮点用高精度字符串硬算每次乘 10 加进位复杂度也要 O(n) 甚至更高。如果题目里 n 给到 10^7这种写法基本就等着超时了。所以这道题真正考你的不是“会不会除法”而是“在不用高精度、不用浮点的情况下你还能不能算出小数点后指定位的数字”。这背后对应的是信息学奥赛里非常核心的一个思想把抽象的数学计算转化成一步一步可以精确控制的算法过程。1.2 为什么不能直接把余数转成小数还有同学会想那我能不能把 a % b 求出来然后这个余数除以 b不就是小数的“种子”吗思路对了一半但光有种子还不够。我给你举个例子a 1b 7n 3。1 ÷ 7 0.142857……小数第 3 位是 2。如果你只算 1 % 7 1然后想要第 3 位你需要经历第 1 位1 × 10 1010 ÷ 7 1余 3。第一位是 1。第 2 位3 × 10 3030 ÷ 7 4余 2。第二位是 4。第 3 位2 × 10 2020 ÷ 7 2余 6。第三位是 2。发现规律了吗每算一位你要做两件事把上一次的余数乘 10再除以 b 得到当前位数字然后保留新的余数进入下一位。这个过程本身就是“除法竖式”的逐位展开。很多教程会含糊地说“用余数模拟除法”但很少有人解释为什么这样模拟就一定能得到正确结果。这里的关键是除法竖式里每一位的确定完全由“当前被除数余数 × 10”决定而这个被除数只依赖上一个余数不依赖之前的任何信息。换句话说这是一个“状态转移”的过程上一轮的结果就是下一轮的输入。想清楚这一点代码就水到渠成了。2. 核心思路把除法还原成手工笔算2.1 竖式除法的本质每一步都在处理“余数”我当年考试数学老师教我们做小数除法时一定说过一句话“余数不变继续除。”比如你用竖式计算 1 ÷ 31 除以 3 不够除商 0余 1然后在余数 1 后面补一个 0变成 1010 ÷ 3 3余 1再补一个 0还是 10 ÷ 3 3余 1。所以 1 ÷ 3 0.3333……。用符号表示就是设当前余数为 r初始时 r a % b。为了求小数点后的第一位我们把 r 乘 10作为新的被除数当前位数字 digit (r × 10) / b下一位的新余数 r (r × 10) % b然后让 r r重复上面的过程。每重复一次就得到下一位小数。这个算法最漂亮的地方在于它只涉及整数乘法和整数除法没有浮点误差没有溢出风险只要控制好数据范围而且每一步的耗时是 O(1)。要求第 n 位就循环 n 次总复杂度 O(n)。有人会问为什么不用一开始的 a 直接乘 10^n因为你想要的是“第 n 位”这个局部信息而不是整个小数。既然每一位的生成只依赖上一位的余数那我一路推下去就行不需要把中间所有位都保存。这种“滚动更新”的思路在信息学奥赛里太常用了比如递推、DP、矩阵快速幂本质上都是“我只关心当前状态和下一个状态”。2.2 为什么这个算法不会爆精度再说细一点。假设 a、b、n 的范围都在 int 能表示的范围内比如 a, b ≤ 10^9n ≤ 10^7r 永远是小于 b 的余数所以 r × 10 最多也就是 10^10 这个量级用 long long 存绰绰有余。但如果你不小心写成long long t a; for (long long i 1; i n; i) { t * 10; // 这样直接乘n 一大就炸 t % b; }这其实也不是不行但要注意 t 在取模之前可能超过 long long。假设 a 10^18b 很小t * 10 会变成 10^19超了 long long 的范围结果就变成未定义行为。正确做法是一开始就做 r a % b把 a 压缩到 b 以内也就是我上面写的那个版本。这一行“先取余再循环”就是很多同学 AC 和 WA 的分界线。你想想a % b 之后r 最大也只有 b-1再乘 10 也不可能超过 b × 10只要 b 在 10^18 以内long long 就稳了。这也是为什么我写代码时第一句永远是 r a % b而不是直接用 a。2.3 别忘了边界n 1 和刚好除尽的情况还有一个容易忽略的问题第 n 位到底是“从小数点后第 1 位开始算”还是“从第 0 位开始算”题目里说了n 是正整数第 n 位小数。所以当 n 1 时我们要的是小数点后第一位。按照循环写法for (long long i 1; i n; i) { r * 10; digit r / b; r % b; }第一次循环算出的 digit 就是小数点后第 1 位。循环 n 次以后digit 就是第 n 位。这里如果你用的是 for (i 0; i n; i)其实也等价因为循环次数相同只是计数起点不同。真正会出错的是那些把 n 减 1 的操作比如“先求第 n-1 位再乘 10 求下一位”很容易在边界上差一位。另一种特殊情况是除尽。比如 a 2b 42 ÷ 4 0.5余数在第 1 位之后变成 0。后续每一位都是 0算法依然成立。不信你试r 初始为 2第一次循环 r 20digit 5r 0第二次循环 r 0digit 0r 0。完美输出 0。所以不用单独判断“除尽”这个分支循环自然会处理。3. 完整实现从分析到 AC 的代码全过程3.1 C 版本一段能直接交的代码直接看我常用的版本注释都写在关键位置#include cstdio int main() { long long a, b, n; scanf(%lld%lld%lld, a, b, n); long long r a % b; // 初始余数把大整数压缩到 b 以内 long long digit 0; for (long long i 1; i n; i) { r * 10; // 余数补零变成下一位的被除数 digit r / b; // 当前这一位小数的数字 r % b; // 产生新的余数进入下一位 } printf(%lld\n, digit); return 0; }这版代码我实测下来在 a、b 不超过 10^9n 在 10^6 以内的情况下运行时间肉眼几乎感知不到。为什么因为循环里只有乘法、除法、取模都是 CPU 的基本运算。n 到 10^7 时大概是 0.1 秒级别依然能过绝大多数题目。如果你担心 b 也可能很大比如 b 接近 10^18那么 r * 10 有可能超过 long long。稳妥一些可以把 r * 10 改成先判断一下 r 和 b 的大小关系或者干脆用 __int128GCC 环境支持__int128 tmp (__int128)r * 10; digit tmp / b; r tmp % b;不过一本通这道题的数据范围一般没那么变态用 long long 就好。真正要担心的是另一种情况n 太大大到连 O(n) 都跑不动这个我在后面第五节专门讲。3.2 题外话为什么我用 scanf 而不是 cin这里插个老生常谈的细节。信息学奥赛的代码输入输出尽量别用 cin/cout 的默认同步模式因为 C 的 iostream 为了兼容 C 的 stdio默认做了很多额外工作导致读入变慢。虽然现在很多评测环境支持关闭同步流ios::sync_with_stdio(false); cin.tie(0);但刷一本通这种老题集时我习惯直接 scanf/printf反正代码也不复杂不需要 C 的面向对象特性。如果你喜欢用 cin记得把上面两行加上否则大数据输入时可能莫名其妙超时。输出方面printf 里用 %lld 输出 long long别忘了 lld 的格式。不少同学写 %d 输出 long long在小数据时碰巧没问题数据一大就出现灵异数字这种坑排起来特别浪费时间。3.3 Python 版思路高精度不是偷懒理由可能有同学用 Python 写这道题因为 Python 的整数是任意精度的所以可以这么干a, b, n map(int, input().split()) # Python 自带高精度但别直接算 a / b 再用字符串截取 # 那样遇到循环小数和特别大的 n 都会很尴尬 r a % b digit 0 for _ in range(n): r * 10 digit r // b r % b print(digit)但 Python 的循环跑得比 C 慢n 到 10^6 还能接受到 10^7 就开始卡了。所以我的建议是信奥比赛优先掌握 CPython 更适合平时验证思路。你要是想用 Python 偷懒直接算 a / b 然后用 Decimal 高精度也可能出问题因为高精度能保证的是“有效位数”不是“无限小数某一位”。所以即便 Python 支持大整数这个“逐位推余数”的思路依然是最稳的解法。4. 踩坑记录与边界情况速查4.1 我见过最多的几个翻车点第一个坑是余数初始化的位置。很多人写成 r a然后第一个循环里直接 r * 10这样算出来的其实是整数部分的数位差了一位。可以先在纸上算一下 3 ÷ 8 0.375 的第 1 位是几再对比代码输出马上就能发现问题。第二个坑是循环次数算错。我见过有人写for (long long i 0; i n - 1; i) { ... }这等于只推了 n-2 轮最后输出的是第 n-1 位。为什么会有这种错误因为脑子里的“偏移量”没理清。最稳妥的方法就是循环 n 次什么都不用偏移第 i 次循环结束时的 digit 就是第 i 位。第三个坑是 long long 格式化输出。前面也提过printf 写 %d 输出的只是低 32 位long long 被截断数字直接错乱。这个错误不会报编译错纯靠人眼排查真遇上了非常头疼。第四个坑比较隐蔽如果 a 或 b 是负数怎么办。一本通这道题一般保证是正整数但为了防止意外可以在开头处理一下符号if (b 0) { a -a; b -b; } long long r a % b; if (r 0) r b; // 让余数转为非负方便后续判断信奥题里“正整数”是常见约束但升级打怪的时候你会遇到各种鬼畜输入养成“输入先取正、余数转非负”的习惯能帮你躲掉不少雷。4.2 边界情况对照表我直接把平时会用来对拍的边界样例整理成一个表你自己测的时候照着跑一遍就行测试用例期望输出说明1 3 131÷30.333…第1位是31 3 1003循环小数第100位还是32 4 152÷40.5第1位是52 4 1000除尽后余数为0后续全是01 2 151÷20.5第1位是57 6 267÷61.1666…第2位是61 7 771÷70.1428571…第7位是1还是7手算一下循环节为142857第7位又回到1。这里你要小心我的例子写的是第7位期望输出其实是1如果你按“循环节长度”推算会得到1而不是7。这个表里 1 7 7 那行很多人会算错。1÷7 的小数0.142857142857……第1位1第2位4第3位2第4位8第5位5第6位7第7位又回到1。所以正确答案是 1而不是 7。这种“循环节首尾相接”的边界最容易暴露你对第 n 位的定义是否清楚。4.3 对拍思路怎么验证自己写的对不对平时刷题最忌讳只看题目样例。样例过了不等于代码对了尤其这种边界问题特别多的题。我一般会写一个暴力版本直接用高精度字符串模拟除法和一个高效版本然后随机生成 a、b、n比较两个版本输出是否一致。举个例子Python 里可以很轻松写一个暴力版from decimal import Decimal, getcontext def brute(a, b, n): getcontext().prec n 10 s str(Decimal(a) / Decimal(b)) # 小数部分从 . 后面开始 dot s.index(.) return int(s[dot n])这个暴力版本在小数据下可以用来验证 C 程序的正确性。注意 Decimal 的精度要留足否则小数点后面直接被舍入暴力结果本身就不准了。等你验证完随机数据再把边界样例过一遍基本就可以放心提交了。5. 扩展一步n 很大的时候怎么办5.1 抽屉原理余数必然循环前面说的 O(n) 循环在 n 是 10^7 时还顶得住但如果 n 是 10^12甚至 10^18 呢你不可能真的循环一亿亿次这时候就要找规律了。小学奥数我们都学过任何分数要么能化成有限小数要么能化成无限循环小数。为什么因为长除法过程中余数 r 始终满足 0 ≤ r b一共只有 b 种可能。你每走一步就会产生一个新的余数当某个余数第二次出现时后面的过程就会完全重复第一次出现之后的过程。也就是说小数部分一定进入循环。这背后的原理叫抽屉原理鸽巢原理余数只有 b 个抽屉你走了 b1 步至少有两个余数相同。这个相同点就是循环节的起点和终点。顺着这个思路我们可以把算法优化到 O(b) 的预处理加上 O(1) 的查询。5.2 循环节优化的完整写法先看一个能用的 C 实现。我用一个数组 firstPos 记录“某个余数第一次出现的位置”再开一个 remAtPos 数组记录“每个位置对应的余数”这样发现循环后可以直接回退到循环起点#include cstdio #include cstring const int MAXB 1000005; int firstPos[MAXB]; // 余数 r 第一次出现的位置-1 表示未出现 long long remAtPos[MAXB]; // 位置 i 对应的余数用于回退 int main() { long long a, b, n; scanf(%lld%lld%lld, a, b, n); if (b 0) { a -a; b -b; } long long r a % b; if (r 0) r b; memset(firstPos, -1, sizeof(firstPos)); int pos 0; int curDigit 0; // 先按正常流程推位同时记录余数位置 while (pos n) { if (firstPos[r] -1) { firstPos[r] pos; remAtPos[pos] r; r * 10; curDigit r / b; r % b; pos; } else { // 发现余数重复说明从这里开始进入循环 int start firstPos[r]; int cycle pos - start; // 循环节长度 long long remain n - pos; // 还需要推的步数 long long steps remain % cycle; // 只需要在循环节内走这么多步 r remAtPos[start]; for (long long i 0; i steps; i) { r * 10; curDigit r / b; r % b; } printf(%d\n, curDigit); return 0; } } // 如果因为 n 比较小还没发现循环就结束了 printf(%d\n, curDigit); return 0; }梳理一下逻辑正常推位到第 pos 位pos 从 0 开始所以循环结束后 curDigit 就是第 pos 位。如果当前余数 r 之前出现过那就没必要再一位一位推了。循环节起点是 start当前是 pos所以循环节长度 cycle pos - start。离目标还有 remain n - pos 步直接在循环节里取余数即可。于是把 r 回退到循环起点对应的余数再走 steps 步得到答案。这个版本的时间复杂度是 O(min(n, b))空间复杂度 O(b)。当 b 不太大时即使 n 是 10^18也能秒出结果。我拿 1 7 10^18 试过输出是 7因为 1÷7 的循环节长度是 610^18 除以 6 的余数是 4循环节第 4 位对应 8……等等我口算容易出错还是以代码运行为准。不过思路是成立的。5.3 什么时候不推荐这个优化如果 b 特别大比如 b 10^9开一个 size 为 10^9 的数组是不现实的内存直接爆掉。这时候要么压缩余数值域比如用哈希表记录位置要么放弃预判循环节老老实实 O(n) 跑赌题目数据没那么狠。还有一种思路是找分母分解质因数后的规律判断纯循环还是混循环但这就有点深了不适合新手。更实际的做法是写一个“自适应”版本先设置一个阈值比如步数走了 10^6 还没有发现循环就证明 b 的规模很大循环节可能非常长再走下去可能超时。但信奥题一般不会故意卡这种点真遇上了就说明题目不止考“求小数某一位”而是考数论思维那又是另一篇文章的内容了。我个人在实际刷题中的体会是不要把循环节优化当成标准解法死记硬背先把最朴素的“余数模拟法”写熟写透。因为它在绝大多数小题里已经够快而且代码简单、不容易出错。等哪天真遇到 n 大到离谱的加强版再临时上循环节优化也不迟毕竟思路框架你已经掌握了。最后再分享一个小技巧如果你不确定某道题能不能直接用浮点数偷懒就在草稿纸上手算一个循环小数比如 1÷7 的前几位再用你的代码输出对比。几秒钟就能验证你的算法到底在“做什么”比自己盲目试错高效得多。这道题虽然简单但“余数驱动计算”的思维往后学高精度除法、进制转换、同余定理都会反复用到值得多花十分钟想透。