1. 题目解读高精度除法到底在考什么1308这个编号在信息学奥赛一本通里属于基础算法章节的经典题目对应的是高精度运算里的除法。很多初学者学到高精度加减法的时候还挺顺利一到除法就卡住因为除法跟前三个运算的套路完全不一样加减乘都是竖式直接模拟除法要做的是试商背后藏着一层层判断和循环。这篇内容我就围绕高精除这个主题把思路、代码、边界情况一次讲透。先说清楚这道题解决什么问题给你两个位数可能达到几百甚至上千的大整数a和b让你输出a除以b的商和余数。普通int和long long根本装不下这么长的数字所以必须用数组自己模拟一个竖式除法。学这个知识点的人主要是刚接触算法竞赛的初学者以及正在刷一本通、OpenJudge入门题的学生。它看起来只是一个独立题目但理解了高精除之后学大数运算的压位优化、二分试商甚至后面某些字符串模拟题都会轻松很多。顺带说明一下我按最常见的题面约定来写第一行输入被除数a第二行输入除数b输出第一行是商第二行是余数。如果你用的OJ只要求输出商那把余数输出那一段删掉即可核心算法完全一样。2. 高精除的两种形态先搞清楚你的除数是什么量级高精度除法根据除数的类型代码难度差很多。很多初学者没分清这两类拿着高精除高精的代码去写除低精的题又长又容易错反过来用除低精的思路处理高精除数也会直接翻车。2.1 高精度除以低精度本质是一层递推如果除数是一个普通的int甚至long long范围内的数问题就简单多了。比如求一个500位的数除以12345的商和余数不需要搞复杂的竖式模拟。我们从被除数的最高位往低位走维护一个当前余数每一步做两件事把当前余数乘以10再加上被除数当前这一位的数字用这个拼好的数除以低精度除数整数部分就是商在这一位的值新的余数就是取模结果。这个思路其实就是小学数学里除法竖式的横式版。举个小例子12345除以7。从最高位1开始余数11 7商位0下一位拼成1*1021212/71余5再下一位拼成5*1035353/77余4再拼4*1044444/76余2最后拼2*1052525/73余4。商1763余4手动验算一下完全正确。代码非常短核心就一个循环#include iostream #include cstring using namespace std; const int MAXN 1005; char s[MAXN]; int a[MAXN]; long long b; int ans[MAXN]; int main() { cin s b; a[0] strlen(s); for (int i 1; i a[0]; i) a[i] s[a[0] - i] - 0; long long r 0; // 当前余数 for (int i a[0]; i 1; i--) { r r * 10 a[i]; ans[i] r / b; r % b; } int len a[0]; while (len 1 ans[len] 0) len--; for (int i len; i 1; i--) cout ans[i]; cout endl; cout r endl; return 0; }注意余数r每一步最大不超过b的10倍所以用long long存b对绝大多数竞赛题目都够了。如果b能达到1e9量级r一路乘10理论上最多到1e10long long照样扛得住。2.2 高精度除以高精度必须模拟完整竖式当除数本身也是几百位的超大数时上面这套递推就失效了因为你没法对一个大数组直接做除以b和取模。这时候要回到竖式除法的本源逐位试商。竖式除法的本质动作其实就两个拼数和试商。拼数就是每次从被除数取一个新位接到当前余数的末尾相当于余数乘10加新位试商就是看看当前这个数里最多能包含几个除数商的那一位就记几然后把除数的这个倍数从当前数里减掉剩下的作为新余数进入下一轮。关键在于看最多能包含几个除数这件事程序里没法直接算因为我们没有大数除法指令。所以笨办法就是循环减法从当前数里反复减除数每减一次商加一直到当前数小于除数为止。由于每次拼数后的当前数一定小于10倍的除数上一轮余数小于除数乘10加一位后最大也就10b-1所以每一轮最多减9次效率完全可控。这个用减法代替除法的思路是整道题的核心也是初学者最容易绕不过去的弯。你可能会问循环减法这么笨效率行吗分析一下就知道商的每一位最多做9次减法被除数最多n位每次减法最多处理m位总复杂度就是O(9*n*m)n和m在一千以内时完全没问题评测机跑得飞快。3. 存储结构与三个辅助函数先把地基打牢高精除高精不像除低精那样几行搞定它需要几个基础函数配合分别是比较函数、减法函数、以及主流程里的移位拼接操作。这三个东西每一项都有坑我拆开讲。3.1 倒序存储为什么下标1存个位写高精度算法几乎所有模板都用数组下标从1开始a[0]存位数数字倒序存储的方式。也就是说数字12345存到数组里是a[0] 5表示这个数有5位a[1] 5个位a[2] 4十位a[3] 3a[4] 2a[5] 1最高位这么存的原因是加减乘的进位和借位都是往高位方向走的倒序存储时操作连续、不容易越界。做除法时虽然主流程是从高位往低位扫但试商过程中不断用到比较和减法这两个函数按倒序处理最顺手。所以统一用倒序存储除法里只是读取顺序变一下内存布局不用改。字符串转成数字数组的代码基本是固定模板a[0] strlen(s1); for (int i 1; i a[0]; i) { a[i] s1[a[0] - i] - 0; }这里s是字符数组s[a[0]-i]是正序字符串的第i-1位减掉0得到数字。比如s1123s1[0]1a[3]1。3.2 比较函数长度优先值为辅高精度比较的核心逻辑很简单先比长度长度大的数一定大长度相等时从最高位数组最后一个有值的位置往低位逐位比。int compare(int a[], int b[]) { if (a[0] b[0]) return 1; if (a[0] b[0]) return -1; for (int i a[0]; i 1; i--) { if (a[i] b[i]) return 1; if (a[i] b[i]) return -1; } return 0; }约定返回值a大于b返回1a小于b返回-1相等返回0。这个函数在除法主流程里用来判断当前余数是否还大于等于除数是整个试商循环能否正确退出的关键。有个隐蔽的坑如果某个数在最前面几位是0比如00123按字符串处理时长度是5但实际有效位数是3。所以每次操作完必须做去前导零把虚高的长度缩回来。具体做法是一个while循环while (a[0] 1 a[a[0]] 0) a[0]--;注意a[0]最少保持1即使数字是0也要保证长度为1否则后面输出余数时会什么也打不出来。3.3 减法函数借位处理是灵魂高精度减法也是基础中的基础但要保证它能在除法里安全调用得注意两点一是调用前必须确保被减数不小于减数二是借位过程必须把数组后面的位也处理干净。void subtract(int a[], int b[]) { for (int i 1; i a[0]; i) { a[i] - b[i]; if (a[i] 0) { a[i] 10; a[i1]--; } } while (a[0] 1 a[a[0]] 0) a[0]--; }这段代码里b[i]在i超过b[0]时是0因为全局数组初始化后所有位置都是0所以循环到a[0]是安全的。借位那里如果a[i]减完是负数就向高位借1当10加上来同时a[i1]减1。因为倒序存储进位方向就是i1完全不用额外判断。为什么这里不写按b[0]循环因为调用减法时a的位数一定不少于b否则compare会拦下来所以直接按a[0]循环让b[i]自动用0补齐代码省事。4. 高精除高精主流程完整代码逐行拆解准备动作做完主流程其实只有三步正好对应竖式除法的 拼数、试商、记商。我先把完整代码贴出来再一步一步解释为什么这样写。#include iostream #include cstring using namespace std; const int MAXN 1005; char s1[MAXN], s2[MAXN]; int a[MAXN], b[MAXN], c[MAXN]; int tmp[MAXN]; // 当前余数 int compare(int a[], int b[]) { if (a[0] b[0]) return 1; if (a[0] b[0]) return -1; for (int i a[0]; i 1; i--) { if (a[i] b[i]) return 1; if (a[i] b[i]) return -1; } return 0; } void subtract(int a[], int b[]) { for (int i 1; i a[0]; i) { a[i] - b[i]; if (a[i] 0) { a[i] 10; a[i1]--; } } while (a[0] 1 a[a[0]] 0) a[0]--; } int main() { cin s1 s2; // 除数为0属于非法输入题目一般保证不出现但写上更稳 if (strlen(s2) 1 s2[0] 0) { cout 除数为0 endl; return 0; } a[0] strlen(s1); b[0] strlen(s2); for (int i 1; i a[0]; i) a[i] s1[a[0] - i] - 0; for (int i 1; i b[0]; i) b[i] s2[b[0] - i] - 0; // 竖式除法核心 for (int i a[0]; i 1; i--) { // 第一步拼数把当前位a[i]接到余数tmp末尾 for (int j tmp[0]; j 1; j--) tmp[j1] tmp[j]; tmp[1] a[i]; tmp[0]; // 第二步去掉tmp的高位前导零 while (tmp[0] 1 tmp[tmp[0]] 0) tmp[0]--; // 第三步试商反复减除数每减一次这一位商加1 while (compare(tmp, b) 0) { subtract(tmp, b); c[i]; } } // 输出商 int len a[0]; while (len 1 c[len] 0) len--; for (int i len; i 1; i--) cout c[i]; cout endl; // 输出余数 for (int i tmp[0]; i 1; i--) cout tmp[i]; cout endl; return 0; }我挑几个关键点细说。4.1 拼数操作tmp的移位原理tmp保存的是当前余数。每次进入循环要把上一轮得到的余数整体往高位方向挪一格腾出最低位来放a[i]然后再把a[i]放进去。因为数组是倒序的tmp[1]是个位往高位挪就是下标变大for (int j tmp[0]; j 1; j--) tmp[j1] tmp[j]; tmp[1] a[i]; tmp[0];举个例子上一轮tmp是5tmp[0]1tmp[1]5a[i]7这一轮执行完tmp变成tmp[1]7tmp[2]5。按倒序读就是数字57正好等于5*107。这个操作就是你手工列竖式时把余数拉下来再补一位的动作。很多人会疑惑tmp的长度会一直增长会不会超出数组范围不会。因为每一轮试商结束tmp被减到小于b长度最多和b相同。下一轮拼数后tmp最多比b多一位。b最长1000位tmp最多1001位开着1005的数组完全够用。不过写代码时要留够余量比赛里有人开MAXN505却输入1000位数据下标直接越界这种错在本地根本测不出来一提交就是运行错误。4.2 为什么拼完数必须去前导零这一步很多人不当回事但它直接影响compare的正确性。假设上一轮余数被减成了0tmp[0]1tmp[1]0。拼数时先移位再把a[i]放进来。如果a[i]3拼完应该是3。可tmp是从0拼成的03数组里tmp[1]3tmp[2]0tmp[0]2。去前导零的while会把tmp[0]从2缩回1这样compare才能正确把03当成3来比。如果不做这步tmp[0]2compare(tmp,b)时如果b的位数正好是1就会先比长度得出03 b的错误结论导致下面减法时tmp位数不够减法函数读b[2]时读到0倒是没事但整个试商逻辑就乱了。这个坑我在新手代码里见过太多次症状五花八门建议直接记住凡是对tmp做改动之后都顺手去一次前导零成本极低收益极高。4.3 试商循环减法代替除法的边界试商的核心while很简单while (compare(tmp, b) 0) { subtract(tmp, b); c[i]; }每执行一次tmp就减掉一个b同时当前商的第i位加1。当tmp小于b时说明这一位试商结束进入下一位。前面分析过每轮试商最多执行9次减法所以c[i]一定在0到9之间。为什么一定不超过9因为进入本轮时tmp是上一轮的余数上一轮结束时我们就保证了tmp b所以本轮拼数后tmp 旧tmp * 10 a[i] 10*b。如果这一位商等于10意味着tmp 10*b矛盾。所以c[i]最多9存进int数组没问题输出时也不需要额外的进位转换。4.4 输出商和余数的细节商数组c[i]初始全是0c的位数最多和被除数相同。输出前要跳过前导零但注意至少要输出一位0。比如5除以7商就是0c数组里全是0len要被缩到1然后输出c[1]0这样才对。余数就是最后tmp里存的东西。试想整个流程走完后tmp经历了一轮又一轮的拼数减b最后剩下的就是整个除法做完的余数。输出时从tmp[tmp[0]]到tmp[1]挨个打印即可tmp[0]最少是1所以不会出现空输出的情况。5. 边界数据与测试怎么验证代码是对的写完了代码不能直接交上去就完事。高精度题最容易在边界上翻车我有自己固定的测试清单这里分享给大家照着测一遍基本能规避大部分问题。5.1 测试用例设计清单用例输入预期行为说明普通整除1000000000 / 100商10000000余数0大数整除验证进位与商的位数被除数小于除数123 / 456789商0余数123商为0的边界除数是一位数9876543210 / 7商1410934744余数2验证不出现商位溢出前后均带零1000 / 10商100余数0验证前导零处理相等数字123456789 / 123456789商1余数0比较函数等于分支极长数据999...9500位/ 3商333...3余数0压力测试验证数组上限余数非零131 / 17商7余数12常规非整除测试时我建议把除数和被除数直接复制到输入文件里一行一个不要手输手输500位数字多打一位少打一位都难查。5.2 时间复杂度估算设被除数有n位除数有m位商的每一位需要做最多9次减法总共n位每次减法最多处理m位数字总运算量约O(9*n*m)。nm1000时大约9*10^6次数字操作对C来说就是几毫秒的事。如果n和m都到5000运算量会飙到2亿多标准十进制的模拟就会有点吃力这时要考虑压位优化下面会讲。5.3 评测环境的一点提醒我在本地测试过1000位除以999位的极限数据代码运行稳定。提交到OJ时注意数组大小MAXN至少要比题目给的上限大一点。一本通这类题给的位数一般不超过500开1005已经完全够用。数组大一点没坏处但也不能大到离谱导致栈溢出全局数组没这个问题放心用。6. 常见问题与排查技巧写高精除下面这几个问题是我见过的高频翻车点整理成速查表哪个对不上就重点查哪里。症状可能原因排查方法输出商前面多了一串0输出去前导零的while写错了检查while条件是否保留最后一位输出结果为0但实际不是数组长度被错误缩到1检查所有去前导零的位置是否过度运行时崩溃数组越界检查MAXN是否够大tmp移位是否超出边界商中间某位大于9或出现负值试商循环退出条件错误或tmp前导零没处理在while里加打印观察tmp和c[i]输出余数为空tmp[0]被缩成0去前导零时保留1位下限除数为0时行为异常缺少特判输入后立刻判0我自己调试时的习惯是在compare和subtract入口打印关键变量的长度和值虽然笨但对找bug特别有效。比如怀疑试商不对就打印进入while前tmp的值和b的值手动算一遍该减几次对比c[i]是否一致基本上几个用例下来就能定位问题。还有一个小技巧写一个对拍脚本用小范围的随机数保证在int范围内生成a和b用普通除法算出期望结果再和你的高精程序输出对比。这个方法在算法竞赛里叫对拍十分钟就能写出来比肉眼盯代码强一百倍。第一次对拍能跑一万组不挂代码基本就稳了。7. 优化方向二分试商与压位存储高精除的基础写法已经能应付绝大多数题目但如果数据范围变大比如被除数达到一万位或者比赛时限特别紧有两个优化方向值得了解。7.1 二分试商把最多9次减法变成log级别前面说每轮试商最多减9次常数很小。但注意这个9是十进制下的结论。如果我们用二分法来确定商位的值就可以在0到9之间快速定位先猜5比较tmp和5*b的大小如果tmp大于5*b就再试7或8否则试2或3。比较仍然用高精度比较但需要先算b的某个倍数这又涉及到高精度乘低精度的操作。对于n、m较大的场景二分试商能明显减少减法调用次数代码复杂度也上了一个台阶。7.2 压位存储把int数组当万进制用目前我们的数组每个位置存0到9的一位数字空间利用率低。压位优化是让每个数组位置存0到9999也就是四位数字。加减乘除的进位借位从10变成10000代码里的乘10改成乘10000小于10的判断改成小于10000。这样存储密度提高4倍运算量也减少到原来的四分之一左右。压位以后比较函数、减法函数的主体逻辑不变但边界判断和进位处理的常数要仔细改。我建议初学者先把不压位的版本写对再考虑优化。7.3 什么时候值得优化我个人经验是位数在2000以内基础十进制模拟完全够用位数超过5000必须考虑压位或者二分试商。刷一本通这类入门题库基础写法能秒过不需要额外折腾。但如果你打算参加进一步的竞赛压位几乎是必会技能因为它能让你在同样的时限里处理更大规模的数据属于性价比很高的升级方向。8. 一点个人经验我当初学高精除时最难迈过去的坎就是理解为什么要用减法代替除法。后来我用笔在纸上完整列了一个竖式把每一步拼数和试商都标出来再回来看代码瞬间就通了。这个方法我想推荐给每个卡住的人别直接啃代码先拿笔算一个简单的除法把每一步做什么写下来再对应到程序的变量上。另外多说一句这种基础算法题一遍AC不算本事能自己把代码完全讲明白才算真的会。我给身边同学讲高精除的时候发现大部分人听过一遍觉得懂了但合上代码自己写就漏洞百出。最好的练习方式是不看模板从零开始写卡住了再回来看卡住的点往往就是你最薄弱的地方。把高精除彻底吃透后面遇到再复杂的模拟题你都会有底气。