GESP 5级备考群里最常见的求助帖是什么不是排序不是二分查找而是高精度加法写着写着就出问题。很多人觉得高精度算法就是个模拟竖式思路全会一写就废。这个现象特别奇怪——算法本身不难难的是和它绑在一起的那些语法细节字符串转数组、倒序存储、数组清零、进位借位、去前导零每一个环节都是失分点。这篇文章我就按自己带学生备考GESP 5级的经验把高精度算法涉及的语法知识、四则运算实现和进阶方向从头到尾梳理一遍。目标读者很明确正在准备GESP 5级、或者学过C但一写高精度就发懵的同学。文章里的代码都是完整可跑的每个实现我会解释为什么这么写、出问题会出在哪里。看完之后你不光能写对高精度还能明白为什么之前的代码会错。1. GESP 5级为什么把高精度算法当考点1.1 从考纲看高精度的位置GESP全名青少年软件编程等级考试由中国计算机学会主办一共8个级别。1到4级主要覆盖C基础语法、顺序分支循环、函数、数组、字符串这些内容说白了就是在考你会不会写代码。到了5级考纲明显转向你会不会想算法高精度计算、排序、二分查找这些经典算法开始成为主角。我个人的看法是5级是一个分水岭——语法已经够用接下来拼的是把语法组合成方案的能力。高精度计算在这个阶段被反复考察不是因为它难而是因为它非常考验考生的基本功。一道高精度加法题表面上只需要模拟竖式实际上把字符串处理、ASCII码转换、数组下标管理、循环边界、进位逻辑、输出格式全都串在了一起。换句话说高精度是5级阶段性价比最高的复习素材——把高精度搞定相关的语法知识基本就都稳了。1.2 内置整数类型的天花板到底在哪先回答一个基础问题C自带的整数类型到底能装多大的数我把常见类型整理成了下表类型占用字节最大值十进制最多位数int4214748364710long long8922337203685477580719unsigned long long81844674407370955161520没错就算用 unsigned long long也只能表示20位的整数。而GESP 5级的高精度题目经常给你一个长度几百甚至上千位的数——比如让你计算两个200位整数相加或者求一个1000位整数除以一个普通int的商和余数。这种规模用内置类型直接爆掉连讨论溢出方式的资格都没有。那怎么办既然一个变量装不下就把数拆开用数组一个一个格子地装。这就是高精度算法的核心思路。1.3 高精度的本质把上行竖式搬进代码我一直跟学生说高精度算法本质就是我们小学学过的竖式运算搬进代码而已。比如计算 456 789你在草稿纸上会这样写456 789 ------ 1245加法从个位开始6915写5进158114写4进147112写2进1最后最高位还有1。整个过程包含三个关键词从低位到高位、进位、逐位处理。代码要做的事情一模一样。只不过个位、十位、百位这些位置在数组里有对应的下标。我通常会用一个数组a让a[0]存个位、a[1]存十位、a[2]存百位……这样数组下标从低到高正好对应数的低位到高位计算方向跟竖式保持一致。有了这个思想打底后面四则运算的代码就不难理解了。2. 写高精度前必须先啃下的语法底座2.1 字符串读入与ASCII的约定高精度题目的输入格式一般是一行或两行特别长的数字比如123456789012345678901234567890 123456789012345678901234567890这种数用什么读用 int 或 long long 读必然溢出正确做法是把整个数字当作字符串读进来。cin 的字符串输入在这里就派上用场了#include iostream #include string using namespace std; int main() { string x, y; cin x y; // 之后用高精度函数处理 return 0; }cin 遇到空格或换行会自动截断所以一次读一个数刚好。如果一行里有两个数用空格隔开cin x y 也没问题。读进来之后字符串里每个字符都是 char 类型比如字符5在ASCII码表里的值是53。要把它变成数字5直接减去字符0ASCII码48就行char ch 5; int digit ch - 0; // 结果是5反过来要把数字5变回字符5就加上0char(0 5)。这个ASCII约定是高精度算法里最常用的语法点也是新手最容易犯错的点——有人会直接写 int digit (int)ch得到的是53而不是5。2.2 倒序存储为什么必须倒着存我见过不少同学的代码读完字符串之后直接按原顺序存进数组s[0]存最高位s[1]存下一位……看着挺直观但一写加法的进位就傻了。举个例子输入 456字符串下标0是4、1是5、2是6。按原顺序存a[0]4, a[1]5, a[2]6。现在要计算 456789个位6和9分别在a[2]和另一个数组的b[2]你得从数组尾部往前算。进位方向呢个位进位要加到十位上也就是从下标2加到下标1……方向反了非常别扭。所以标准做法是倒序存储让数组下标0存个位下标1存十位依次类推。void strToArr(string s, int a[]) { int len s.size(); for (int i 0; i len; i) { a[i] s[len - 1 - i] - 0; } }比如 s 456len3。循环i0时取 s[2] 6放进a[0]i1取 s[1] 5放进a[1]i2取 s[0] 4放进a[2]。这样整个数组的存储和竖式完全对齐后面加、减、乘处理起来都非常顺。2.3 函数、数组与返回值三个隐蔽坑写高精度时很多人习惯把每道题的完整逻辑塞进main函数代码又臭又长还容易出bug。我强烈建议把四则运算各自封装成函数。封装时会遇到三个坑提前说明坑一数组作为函数参数时会退化为指针。这意味着你可以在函数里修改调用者的数组内容这是优势但也意味着函数里 sizeof(a) 拿不到数组真实大小必须额外传入长度。所以不要想着在函数内部重新计算数组元素个数。坑二不能直接返回局部定义的数组。比如你在函数里 int c[1005]; 算完了想 return c;C会直接报错因为局部数组在函数返回时就销毁了。解决办法有两个要么把结果数组也通过参数传出去要么把结果转成一个 string 再返回。四则运算里我推荐后者——字符串天然适合保存结果也方便最后直接输出。坑三函数传参用值传递会复制整个字符串。高精度题里字符串可能很长复制一次就是一次O(n)开销。GESP题量不大复制造成的浪费可以忽略但更规范的做法是传引用比如 string x既能避免复制也方便在函数内交换两个字符串例如保证减法中x y。这三个坑其实是C语法核心的一部分5级考试里哪怕不写高精度函数和数组的考察也会涉及。搞懂它们等于一箭双雕。3. 加减乘除四件套的逐层实现与要点3.1 加法先把进位处理熟练高精度加法是最基础的我建议直接把它当作标准模板来练因为后面乘法也要用到类似的进位逻辑。完整代码如下#include iostream #include string #include algorithm using namespace std; void strToArr(string s, int a[]) { int len s.size(); for (int i 0; i len; i) a[i] s[len - 1 - i] - 0; } string add(string x, string y) { int a[505] {0}, b[505] {0}, c[505] {0}; int lenA x.size(), lenB y.size(); strToArr(x, a); strToArr(y, b); int maxLen max(lenA, lenB); // 先算每一位的原始和 for (int i 0; i maxLen; i) { c[i] a[i] b[i]; } // 统一进位 for (int i 0; i maxLen; i) { if (c[i] 10) { c[i 1] c[i] / 10; c[i] % 10; } } int resultLen maxLen; if (c[maxLen] ! 0) resultLen; string result; for (int i resultLen - 1; i 0; i--) { result char(c[i] 0); } return result; } int main() { string x, y; cin x y; cout add(x, y) endl; return 0; }这里解释几个关键点。数组为什么定义成 int a[505] {0}505 是根据数据规模估计的位数上限加上一点余量。数组初始化成0非常重要因为后面进位时会用到 c[maxLen] 这个位置如果没初始化读到的是随机脏数据结果直接错。进位循环的写法是先算完所有位置的原始和再统一进位。比如 i0 位置算出15先把 c[1] 加上1等循环到 i1 时c[1] 已经包含了进位的1再继续判断是否大于等于10。这样一层循环就能把进位传递到任意高位。输出时倒着从最高位往低位拼字符串char(c[i] 0) 刚好完成数字到字符的转换。加法的时间复杂度是O(n)n是位数几百上千位的数据毫无压力。3.2 减法借位、比较交换和负号减法比加法多出两个问题结果可能是负数被减数可能小于减数。所以在做减法之前先得判断两个数谁大。判断大小的逻辑很直接位数多的数大位数相同时字符串的字典序比较就等价于数值比较因为0到9的ASCII码递增且位数相同的情况下从左到右逐位比较即可。所以先写一个比较函数bool isGe(string x, string y) { if (x.size() ! y.size()) return x.size() y.size(); return x y; }减法主逻辑string sub(string x, string y) { bool negative false; if (!isGe(x, y)) { swap(x, y); negative true; } int a[505] {0}, b[505] {0}, c[505] {0}; int lenA x.size(), lenB y.size(); strToArr(x, a); strToArr(y, b); int maxLen lenA; for (int i 0; i maxLen; i) { if (a[i] b[i]) { a[i] 10; a[i 1]--; } c[i] a[i] - b[i]; } while (maxLen 1 c[maxLen - 1] 0) maxLen--; string result; if (negative) result -; for (int i maxLen - 1; i 0; i--) { result char(c[i] 0); } return result; }减法中的借位逻辑是逐位进行的如果当前位置被减数小于减数向高位借1相当于自己加10高位减1。你可能会问高位减1之后如果高位本身是0怎么办比如1000-1高位的0会变成-1但在下一次循环中-1小于对应位置的减数0于是继续向更高位借10。这个连锁反应通过整数类型的负数中间态就能完成不需要特殊处理最终结果依然是正确的。去掉前导零是关键。比如 500 - 499 001如果直接输出001就是错的。while (maxLen 1 c[maxLen - 1] 0) maxLen--; 这个循环把最高位的0全部去掉但保留至少一位这样结果0也能正确输出为0而不是空串。3.3 乘法双层循环加统一进位乘法比加法难一个档次但思路依然来自竖式。两位数乘法在竖式里是这么算的A的每一位和B的每一位分别相乘再把所有结果按位置累加。在数组里下标i位置和下标j位置的数字相乘结果应该加到 c[i j] 位置上这一步必须理解透彻。string mul(string x, string y) { int a[505] {0}, b[505] {0}, c[1010] {0}; int lenA x.size(), lenB y.size(); strToArr(x, a); strToArr(y, b); for (int i 0; i lenA; i) { for (int j 0; j lenB; j) { c[i j] a[i] * b[j]; } } int resultLen lenA lenB; for (int i 0; i resultLen; i) { if (c[i] 10) { c[i 1] c[i] / 10; c[i] % 10; } } while (resultLen 1 c[resultLen - 1] 0) resultLen--; string result; for (int i resultLen - 1; i 0; i--) { result char(c[i] 0); } return result; }注意几个细节。c数组的大小要开到 lenA lenB 1因为长度为lenA和lenB的两个数相乘结果最多有lenAlenB位。比如 99 * 99 9801是4位lenAlenB正好等于4。进位循环的边界给到 resultLen 即可如果最坏情况下 c[resultLen - 1] 的进位传递到 c[resultLen]因为数组多开了一位所以仍然安全。在实际计算中比如 999 * 999 998001lenA3lenB3resultLen6最高位在下标5完全够用。乘法复杂度是O(lenA * lenB)。两个1000位的数相乘是10^6次基础操作1秒内轻松搞定。但如果两个数都是10^4位运算量达到10^8就会开始有超时风险——这也是后面压位优化的动机。3.4 除法唯一从高位开始的运算高精度除法的考察形式通常是大整数除以一个小整数int范围内求商和余数。这种除法和竖式一致但方向正好和加法相反——要从最高位开始往下除。string divide(string x, int b, int remainder) { int len x.size(); string result; long long cur 0; for (int i 0; i len; i) { cur cur * 10 (x[i] - 0); result char(cur / b 0); cur % b; } remainder cur; int pos 0; while (pos result.size() - 1 result[pos] 0) pos; result result.substr(pos); return result; }这里不需要把字符串倒序存进数组直接按原顺序逐位处理。核心变量cur相当于当前余数每次把下一位数字拼到cur末尾cur cur * 10 当前数字。然后用cur除以b商就是结果的一位新的余数保留下来继续参与下一位的计算。以 1234 / 5 为例第0位1cur 11/5 0result 0cur 1第1位2cur 1212/5 2result 02cur 2第2位3cur 2323/5 4result 024cur 3第3位4cur 3434/5 6result 0246cur 4余数为4最后去掉前导零得到246余4完全正确。这里有个小技巧cur要定义成long long。因为cur * 10 digit理论上可能超过int范围比如被除数有20位时cur在最后一位之前可能达到10^9量级乘以10再加digit后可能越界。但cur每一轮都会取模取余数所以cur实际始终小于 b * 10不会真正爆掉long long。GESP 5级如果考除法多半会在题目描述里明确输入为一个高精度整数和一个不超过int范围的整数或者反过来让你求两个高精度整数的商这种更少见通常用长除法减法模拟实现。先把除以单整数的情况吃透已经足够应付大部分考试场景。4. 课后训练最容易翻车的几个地方4.1 数组没清零就拿来用第一个翻车点几乎人人遇到。C里局部数组在栈上创建时里面的值是不确定的也就是垃圾值。有同学写完 int a[505]; 直接往里存数字存完第i位后后面没存到的位置是什么答案是随机垃圾值。所以在后续运算中如果某个循环试图访问那些没被赋值的下标比如加法进位到c[maxLen]就会读到乱七八糟的数结果自然不对。解决办法就一行定义数组时统一初始化成0int a[505] {0};这个写法的含义是第一个元素初始化为0其余元素自动补0。我见过很多同学翻车都翻在这个看似不起眼的地方。写高精度题养成数组统一初始化为0的习惯能省一半调试时间。4.2 前导零和全零输入第二个翻车点在于输出格式。减法里最容易出现前导零比如 1000 - 999 1如果不处理结果是0001。乘法里也可能出现比如 123 * 0 0如果结果长度较大直接输出会是000000。去掉前导零的通用思路是找到最高非零位然后从这个位置开始拼接字符串。但要小心如果结果本来就是0至少要输出一个0不能输出空串。所以上面的while循环里加了 result.size() - 1 这个边界条件。还有一个容易被忽略的场景输入本身带前导零。比如题目给了000123和45相加如果你原样转成数组可能会多出多余的位。稳妥的做法是在字符串转数组前先统一去掉所有输入的前导零但至少保留一位。GESP的测试数据未必会这么刁钻但养成防御习惯没坏处。4.3 位数估计错误导致越界高精度算法里的数组越界问题非常隐蔽。加法中如果输入是500位的数结果最多501位数组至少要开到505。乘法更麻烦两个500位数相乘结果最多1000位如果你只开了505的c数组那必炸。所以我一般会把数组大小按输入上限 10来开。如果题目说输入不超过1000位加法开1005就够乘法开2010。多开一点不浪费但少开一位就是隐患。测试时可以用最大规模的数据压一下确认没有越界。另一个越界坑藏在函数参数里。strToArr函数只负责把字符串内容写进a数组它自己并不知道a有多大。如果输入长度超过数组容量写越界也不会立刻报错只会悄无声息地破坏相邻内存。GESP的数据一般比较温和但自己训练时要注意控制输入范围和数组大小。4.4 考试中怎么快速自测在训练阶段我推荐一个非常朴素但有效的自测方法拿几组边界数据反复验。加法测 999...9很多位9 1看进位是否正确测 0 0看输出是否为0测 100000...0 1看最高位是否正常。 减法测相同数相减看是否输出0测 1000...0 - 1看借位是否连续测 1 - 1000...0看负号是否出现。 乘法测两个 999...9 相乘检查进位和结果长度测任意数乘0结果必须为0。 除法测 1 / 1000商0余1测 1000 / 1测正好整除的情况余数必须为0。除了边界数据再随机挑几组普通数据用标准结果比如直接让Python算一遍或者用更大的数据类型算一遍验证。我在本地一般会写一个很短的对比脚本把几组数据的输出和Python结果做比对。不用很高端就能把90%的隐蔽bug揪出来。5. 5级之后压位优化与高精度组合玩法5.1 压位高精度把10换成10000先说明GESP 5级考试里普通高精度已经足够应付绝大多数题目压位不是必选项。但它是一个很好的进阶训练能让你对数组、进制、进位有更深的理解也为后续CSP/NOI做准备。压位的思路特别简单普通高精度每一位存0~9相当于逢10进1压位高精度每一位存0~9999相当于逢10000进1。这样做的好处是同样大小的数组能表示的数字位数多了4倍计算时的循环次数也少了大约4倍。具体实现时有几个细节和普通高精度不一样读入字符串后从右往左按4位一组切分每一组转成一个整数存进数组。比如12345678从右往左分成12和345678或者1234和5678存进a[0]5678a[1]1234。进位判断条件是 c[i] 10000 而不是 10。输出时从最高位开始最高位直接输出整数后面每一位都要补前导零到4位因为一个格子里存的可能是0001。所以输出用 printf(%04d) 或者手动补零。如果不处理前导零压位的输出就会变成1而不是10000。这个细节是压位高精度最大的失分点。我一般建议学生考试写普通高精度完全没问题压位只作为思维训练来写不要在考场上临时用不熟练的技术。5.2 高精度与二分答案的组合题过了5级后面还有6级、7级、8级CSP-J/S也在招手。高精度从来不单独存在它常常作为基础工具和其他算法搭配。最典型的组合是二分答案 高精度判断。举个例子给一个高精度整数n求n的平方根只取整数部分。暴力做法是从1试到n当然不行。正确思路是二分答案区间[1, n]每次取mid判断mid * mid是否大于n。mid本身可能就是一个长达几百位的数mid * mid更是大得离谱必须用高精度乘法。这个组合思路在CSP-J的这些年里出现过类似题目GESP 6级及以上的题库里也有影子。这种题难在两点一是二分边界要带着高精度比较去写二是乘法之后的结果要和高精度目标值比较大小比较函数又要用到按位比较的逻辑。如果你能把加减乘除四个函数封装好这种组合题就只是调用而已。5.3 一条从GESP到CSP的高精度学习路径最后聊一下我建议的学习顺序也是我自己带学生常走的路径。第一步把四则运算按照本文的顺序各写三遍每一遍都不看参考代码。第一遍能对着本文抄对第二遍能默写出来第三遍要能做到20分钟内独立写出且一次通过边界测试。第二步做题型归纳。准备一个错题本或者电子文档把高精度相关的错题按加/减/乘/除/组合算法分类每个分类记2到3个典型题。复盘时重点看错在哪一步是进位方向反了还是数组越界了还是输出格式错了。第三步把高精度当成工具箱。学二分、学快速幂、学贪心的时候遇到大整数主动想想能不能用高精度拼进去。这样到6级、7级甚至CSP初赛复赛高精度都不会成为你的短板。写到这里有点收不住最后提一个实在的建议。训练高精度时我建议你把自己的代码和一份标准答案同时跑对比输出。别觉得麻烦高精度这种算法错误都是藏在边角数据里的。你把1000位的加法、减法、乘法、除法四套代码都跑通大数据再去考GESP 5级心里会特别有底。再送一个小技巧考场上如果时间紧张高精度加法、乘法这类题先写一个暴力版本用内置类型直接算作为对拍工具——对内置类型虽然存不下大数但可以拿小数据来对比验证高精度代码是否正确。这个小技巧我在练习中用了很多次基本能保证代码逻辑不出错。