1. 为什么“例1.5”是绕不过去的一道坎如果你正在按某本竞赛入门教材的目录往下学大概率会发现章节名字特别直白第二部分、基础算法、第一章、高精度计算然后一口气列出一堆样例题。1308这道“高精除”就在这一排例题里编号看起来平平无奇但它卡住的人比前四道加起来的还多。原因很简单高精度加减法和乘法你都能从低位往高位逐位算方向是统一的写起来就是个模板。除法不一样——它必须从高位往低位推每算一位还要牵扯到“试商”和“余数滚下去”的过程。很多同学学完加减乘之后信心满满结果卡在除法上不是因为代码长而是因为思路没转过弯来。还有一个更现实的问题这套教材配套的在线评测系统里1308这道题的通过率常年不高。不是因为题面有多难而是因为网上能找到的高精度除法模板“能用”的少“能讲明白”的更少。大多数模板直接甩一段高精度除以高精度的代码注释寥寥几行初学者抄都抄不利索。这篇博文就是要把这道题从“我给你代码”讲成“你知道为什么这么写”顺便把你自己动手实现模板的能力也练出来。2. 先把竖式除法的原型刻在脑子里2.1 除法和其他运算最大的不同点手算整数除法比如 12345 ÷ 7我们从来不是从个位开始往前算的。我们会先看“1除以7不够”再取“12除以7商1余5”接着“余数5拉下来变成5353除以7商7余4”一直做到个位结束。这个过程的本质是每一位上都在做一次“小范围的试商”然后更新余数。余数在下一位时要先乘以10再加上被除数这一位原本的数字再参与下一轮试商。商是逐位从高位“挤”出来的每一位商的范围严格限制在 0~9 之间。这个“0~9”非常关键——正因为每一位商最多只需要试10次高精度除法才有高效的模拟空间。如果每一位商都要从1试到9那就是最多9次减法如果你用“二分猜商”更是只需要对数级别次数的乘法比较。总之除法的核心不是“算除法”而是“用减法来猜商猜完再减”。2.2 高精度数用什么方式存学高精度第一个争论就是数组顺序。加减乘为了对齐低位通常把个位存在数组下标0的位置也就是“逆序存”。但除法模拟竖式的过程是顺着数字高位往低位读的所以处理“高精度除以低精度”时很多人喜欢直接按字符串顺序读入从第0位开始逐位处理代码更直接。到了“高精度除以高精度”情况又不太一样反复做减法时需要高精度减法函数而减法函数天然喜欢逆序存。所以你在网上会看到两种写法并存这不是谁对谁错而是两种场景下的习惯差异。我的建议是主函数里统一用逆序存储写比较、减法、乘法都能直接复用但在除低精度的简化写法里顺序遍历字符串其实更清爽。做题时选一种你顺手的别混着来就行。2.3 每一步的数学含义竖式除法的每一步本质上都在做同一件事把当前余数 R 左移一位乘10再加上被除数的下一位数字 d得到当前被除数片段 X R * 10 d然后找一个最大的整数 q0 ≤ q ≤ 9使得 q * divisor ≤ X令 R X - q * divisor这一位的商就是 q。高精度除法的所有代码无论看起来多复杂最后都能拆回这三句话。能理解这三句话后面看任何模板都不会发怵。3. 两套核心实现除低精度和除高精度3.1 高精度除以低精度入门必须掌握的版本“除低精度”指的是被除数可能是个几百位的字符串而除数是普通 int 或 long long 能装下的数。这种题在很多OJ里作为高精度除法章节的“前菜”也是理解竖式除法的最佳载体。实现思路直接对着竖式来把被除数当作字符串读进来从左往右高位到低位逐位处理。维护一个余数 rem初始为0。对于第 i 位数字 digit先让 rem rem * 10 digit那么当前这一位商就是 rem / divisor余数更新为 rem % divisor。把商位存在另一个数组里。全部处理完后去掉商的前导0然后输出。直接看代码#include iostream #include cstring using namespace std; int main() { char s[205]; long long divisor; cin s divisor; int len strlen(s); // 题目保证 divisor 非0 long long rem 0; int quotient[205] {0}; for (int i 0; i len; i) { rem rem * 10 (s[i] - 0); quotient[i] rem / divisor; rem rem % divisor; } // 输出商去掉前导0 int pos 0; while (pos len - 1 quotient[pos] 0) { pos; } for (int i pos; i len; i) { cout quotient[i]; } cout endl; // 如果需要输出余数 // cout rem endl; return 0; }这段代码里quotient[i]对应的就是被除数第 i 位的商位。因为商可能有前导0比如 1234 ÷ 50第一位商就是0所以最后输出前要从第一个非0位开始。如果最终商的第0位也是0但后面全是0说明商就是0上面的 while 条件保证至少会输出一位0不会出现“什么都不输出”的情况。时间复杂度 O(n)空间 O(n)。这个版本是所有高精度除法理解的地基务必自己手写一遍不要只靠眼睛看。3.2 高精度除以高精度两个大数对撞怎么办当除数和被除数都是几百位的大数时显然不能再用上面的整除方法试商了因为你没法用 long long 去存除数。此时最直观的做法是把“试商”变成“反复做高精度减法”。思路仍然是模仿竖式但每次不再用“rem * 10 digit 再除以除数”来求商而是用减法来数当前被除数片段能减多少次除数商就是几。具体流程分三步把被除数 a 和除数 b 都按逆序存进 vector。预处理一个“位移后的除数”也就是把 b 左移若干位让它的位数和被除数的当前剩余部分对齐。这一步相当于竖式里的“把除数挪到合适的数位下面”。从高位往低位枚举位移量 i。每次生成 shift(b, i)然后判断当前剩余被除数是否还大于等于它如果大于等于就减一次商的第 i 位逆序存的第 i 位加1。这里商会出现 0~9 之间的值吗因为移位对齐后除数片段和当前剩余片段位数一样最多只会减9次多减就变成负数了。所以循环内部每位商最多加到9不会死循环。看代码#include iostream #include string #include vector using namespace std; // 比较 a ba、b均为逆序存放 bool cmp(const vectorint a, const vectorint b) { if (a.size() ! b.size()) return a.size() b.size(); for (int i (int)a.size() - 1; i 0; i--) { if (a[i] ! b[i]) return a[i] b[i]; } return true; // 相等也返回true } // 高精度减法保证 a b结果存在 a 中 void sub(vectorint a, const vectorint b) { int carry 0; for (int i 0; i (int)b.size() || carry; i) { int x a[i] - carry; if (i (int)b.size()) x - b[i]; if (x 0) { x 10; carry 1; } else { carry 0; } a[i] x; } while (a.size() 1 a.back() 0) a.pop_back(); } int main() { string sa, sb; cin sa sb; vectorint a, b; for (int i (int)sa.size() - 1; i 0; i--) a.push_back(sa[i] - 0); for (int i (int)sb.size() - 1; i 0; i--) b.push_back(sb[i] - 0); if (sb 0) return 0; // 题目数据一般不含0 // 被除数小于除数商为0 if (!cmp(a, b)) { cout 0 endl; return 0; } int n (int)a.size(), m (int)b.size(); vectorint ans(n - m 1, 0); // 商最多 n-m1 位逆序 for (int i n - m; i 0; i--) { // 构造 b 左移 i 位后的临时数组 tmp vectorint tmp(n, 0); for (int j 0; j m; j) { tmp[i j] b[j]; } // 连续减法统计这一位商 while (cmp(a, tmp)) { sub(a, tmp); ans[i]; } } // 输出商倒序输出并去掉前导0 int pos (int)ans.size() - 1; while (pos 0 ans[pos] 0) pos--; for (int i pos; i 0; i--) { cout ans[i]; } cout endl; // 如果需要余数此时 a 中存的就是余数 return 0; }这段代码是“高精度除以高精度”最经典的写法每一位商都用减法暴力数出来最多9次。所以复杂度大约是 O((n-m1) * m * 10)对于200位以内的数字完全够用。如果数据范围到了几千位暴力减法的效率就会开始吃紧更极限的题一般就要上倍增减法或者二分高精度乘法了。但竞赛入门阶段先把这份模板吃透比一上来就背高复杂度优化方案划算得多。3.3 除高精度的倍增优化思路如果你已经吃透了逐位减法想更进一步可以试试“倍增减法”每次不是只减一个 b 左移 i 位后的 tmp而是先判断能不能减 8 个、4 个、2 个、1 个。这个思想类似把“连续减法”换成“二进制分解”。伪代码大概长这样while (cmp(a, tmp)) { // 从大到小尝试加倍找到最大的 k 使得 a tmp * 2^k // 相应地在商的这一位加上 2^k并在 a 中减去 tmp * 2^k }这样做的好处是每一位商最多做常数级别的次高精度乘法/比较/减法整体复杂度可以降到 O((n-m1) * m * log10(最大值)) 左右。对于超过1000位的大数优势非常明显。不过我不建议新手上来就写倍增版。先把暴力减法版本用自己的话说清楚再优化也不迟。代码能跑通、能讲明白比盲目背一个自己都不懂的“优化模板”有用得多。4. 例1.5高精除的完整解题实操4.1 题面常见形式与输入输出虽然我手上没有原平台的原样题面但“1308【例1.5】高精除”这类题的题面结构几乎是固定的输入两个大数分别是被除数和除数输出它们的整数商部分版本的题面还会要求额外输出余数。常见的输入格式类似于1345678987654321 123456789而输出则是一行商例如10899659如果你不确定自己的版本是不是要输出余数最简单的办法是把代码里计算完剩下的a也就是余数也打印一下看跟样例对不对得上。对得上就留着对不上就删掉。在竞赛里多输出一行是必错所以提交前一定要确认输出格式。4.2 完整解题步骤第一步读题。先确认两点被除数和除数分别有多大题目有没有说“商和余数都要输出”我见过的多数版本只要求输出商但偶尔也会顺手要求输出余数尤其是教材配套的练习里为了巩固竖式概念经常会要求两个都输出。第二步选方案。如果除数是 int 或 long long 范围内的数直接用 3.1 的除低精度模板。但更常见的“高精除”题除数和被除数都是大数所以直接用 3.2 的高精度除以高精度模板更稳。我个人的习惯是不管题面说的除数多大一律按高精度除以高精度来写一劳永逸。第三步写代码。把 3.2 的代码复制到本地替换掉输入输出的格式部分。如果要求同时输出余数就加一行// 此时 a 是余数a 是逆序存储 int posR (int)a.size() - 1; while (posR 0 a[posR] 0) posR--; for (int i posR; i 0; i--) cout a[i]; cout endl;注意如果余数为0上面的循环输出结果是“0”没问题。但是商和余数如果都要输出格式通常是一行中间空格分隔或者换行具体看题面提示别搞错。第四步本地造数据验证。这一步是所有高精度题必须养成的习惯。高精度代码出错率远超普通题你不验证就直接交大概率要赏心悦目地吃一个WA。造小数据的方法很土但非常有效拿普通整数除法当对照。比如你自己算 1234567890123 ÷ 98765用 Python、计算器、或者手算拿到商和余数再用程序跑一遍看输出是否一致。随机生成二三十组数据对拍比自己盯着代码看半天管用得多。4.3 复杂度与数据范围评估3.2 的朴素减法版假设被除数长度 n200除数长度 m20那么循环次数是 (200-201) * 20 * 最多10 次也就大约 36000 次内部数组操作跑起来几乎一瞬间。就算 n1000m500也就 500 * 500 * 10 ≈ 250 万次量级的操作C 完全扛得住。所以对于“例1.5”这种入门题毫无压力。如果哪天你在更高级的比赛里看到 n 和 m 都到 10^5 甚至更大那就不要在朴素版上纠结了直接换倍增版或者更底层的压位优化。5. 实战中踩过的坑和排查技巧5.1 商的前导0处理不当这是高精度除法最常见的错法。很多新手在输出商时用for (int i 0; i len; i) cout ans[i];结果把前导0也输出了比如 1234 ÷ 5678 输出“0000”实际应该是“0”。解决方法是输出前从高位往下找到第一个非0位。记住一条规则如果商的每一位都是0至少要输出一个0。这就是为什么处理时要用while (pos 0 ans[pos] 0) pos--;而不是把所有0都跳掉。5.2 减法和比较函数写反高精度除以高精度依赖高精度减法。减法有个大前提必须保证a b。如果你在sub函数里写了一堆if (a[i] b[i])借位逻辑但调用前没有判断大小减出负数就全盘崩掉。我的习惯是把cmp(a, b)写成“大于等于”判断只有cmp为 true 才敢调sub。这样减法函数内部就可以放心大胆地直接逐位减不需要再处理符号问题。反过来如果你打算把减法写成通用的大数减法支持负数结果那复杂度会直线上升入门阶段完全没必要。5.3 除数为0的情况虽然题目一般保证除数不为0但作为一个成熟的模板还是建议在进入逻辑前判断一下。字符串判断很简单if (sb 0) { // 按题目要求报错或返回 return 0; }不要试图用 long long 去读除数再做判断——除数可能是个几百位的大数long long 装不下。5.4 复制模板时把逆序顺序弄混3.2 的代码里a和b都是逆序存的商ans也是逆序存的但输出时要倒着输出。新手最容易在这里晕头。有个很好用的自查方法在自己代码里加上临时输出把每一步的a、tmp、ans[i]都打印出来跟手算竖式对照。比如算 12345 ÷ 11你手算商是 1122余数是 3。如果程序某一步输出的是 1221 之类八成就是倒序弄反了。5.5 常见问题速查表问题现象可能原因解决办法输出一堆前导0没有找到第一个非0位置输出前跳过头部的0保留最后一个0商少一位或多一位商数组长度开错ans长度设为 n-m1左移从 n-m 开始倒序枚举减法结果出现负数字符减法前没有判断 ab调用 sub 前先跑 cmp或用 while(cmp(...)) 包住输出余数时去掉0后被截断pop_back 时把唯一一位0也删了while 条件写成 size()1 才pop大样例超时朴素减法太慢数据范围大时上倍增版或压位优化5.6 调试技巧对拍学高精度最值得养成的习惯就是“对拍”。方法很简单用 Python 脚本或者你自己写一个小程序随机生成 n 和 m分别计算Python直接a // b你的 C 程序输出商然后逐组比对。如果随机生成的 100 组数据里全部一致你的高精度除法基本就可以放心提交了。这种习惯养成以后不只是高精度之后的贪心、DP、图论都会受益。很多同学以为自己代码写得没问题结果一提交就是WA本质上就是因为没有对拍习惯出了问题也不知道是思路错还是代码错。6. 个人的一点实操体会高精度除法是我当年学基础算法时最“扭”的一章。加减乘都是顺着一个方向推到底唯独除法要从高位往低位反着来第一次写除法时我整整改了三晚上最后发现不是代码问题是思路没理清。后来我把竖式除法的三句话——“余数乘10加下一位、找最大商、更新余数”写在草稿纸上照着这个逻辑一点一点把代码敲出来瞬间就通了。从那以后我教别人高精度也坚持先讲竖式再给代码。最后送你一个实操小技巧写高精度除法之前先把“高精度比较”“高精度减法”两个函数单独写好、测试用熟因为除法模板百分之九十的bug都出在这两个地基函数里。地基稳了商和余数自然会稳。把这套代码理解透整个高精度章节你就打通关了。