点开赛题列表看到“结果可能很大请使用高精度”、“输出不超过 XXX 位的整数”、“答案需要对 10^97 取模”这些字眼心里就要有数了高精度这关蓝桥杯一定会考。不管你是 C/C 组还是 Java/Python 组大整数运算都是一道绕不过去的坎。区别只在于Java 有现成的 BigIntegerPython 的 int 天生无限长而 C/C 选手必须自己手写一套高精度模板。这篇就把我整理多年、在蓝桥杯赛场上实际验证过的模板和踩坑经验一次性分享出来适合备赛选手、算法初学者以及所有被大数问题折磨过的人。1. 为什么高精度是蓝桥杯绕不开的考点1.1 数据范围决定你必须会高精度先看一个很基础的问题int 能装多大大约是 21 亿也就是 2.1×10^9。long long 能装 9.2×10^18看起来很大但阶乘涨得更夸张。50! 大约是 3×10^64已经远超 long long100! 更是达到了 9×10^157。而蓝桥杯里出现阶乘、斐波那契数列、组合数、大数幂的题目数据范围轻轻松松就让你超过 long long 的边界。举几个典型场景n 达到 1000 的阶乘求和结果有几万位。递推题里第 n 项是个大数题目根本不要求取模直接要求输出完整结果。组合数 C(n, k) 的精确值n 到 500结果同样是天文数字。这些题的本质就是高精度运算。哪怕题目本身是考动态规划、递推、贪心只要中间结果爆类型你就必须用高精度把计算接住。1.2 不同语言组别的高精度待遇这里必须说清楚一件事蓝桥杯按语言分组高精度的“待遇”完全不同。Python 选手最轻松因为 Python 的 int 是任意精度直接相加相乘就行不需要自己实现。Java 组有 BigInteger 类提供 add、subtract、multiply、divide、mod、compareTo 全套方法使用起来也比较无脑。但 C/C 组没有内置大整数必须手写。这就导致一个很有趣的现象同样的题目Python 选手几行写完C 选手还在敲模板。但这不代表 C 组吃亏因为 C 手写高精度在性能上通常比 Python 大整数更快尤其在做压位优化后万位级别的数字运算C 明显占优。无论你报哪个组我都建议理解高精度的底层原理。原因很简单有些题目会对大数做特殊变换比如大数取模、大数开方、高精度小数运算这时候原生 API 不一定顺手你得知道内部是怎么回事才能改得动。1.3 高精度题的三种出场方式根据我刷真题和模拟题的经验高精度在蓝桥杯里很少“单独出道”更多是作为其他算法题的组成部分。常见的有三种第一填空压轴题直接要求你输出某个巨大数值。这种题往往没有太复杂的算法核心就是高精度模板的正确性。第二综合题里的中间计算。比如某道模拟题求大数阶乘的末位非零数字或者求大数幂的值先要完整算出大数再从中提取信息。第三和数论结合比如需要计算大组合数精确值再配合取模、质因数分解等操作。无论哪种出场方式你都需要一套正确、稳定、能快速写出来的模板。这不是说让你死记硬背而是要做到肌肉记忆考场上不假思索就能敲出来。2. 高精度的核心设计为什么数字要倒着存2.1 模拟竖式从低位开始高精度算法的本质就是模拟手算竖式。手算加法时从个位开始加满十进一减法从个位开始借位乘法也是从低位到高位逐位相乘。因此数字在数组里的存储顺序很关键。我习惯用 vector 存储下标 0 存个位下标 1 存十位以此类推。比如数字 12345在数组里就是 {5, 4, 3, 2, 1}。这种“低位在前”的存储方式有几个好处进位和借位都在数组尾部扩展不需要频繁移动元素。长度不同的两个数比较、相加时从下标 0 开始处理逻辑更统一。乘法累加时a[i] * b[j] 的结果正好加到 c[ij] 的位置公式简洁直观。如果你反过来“高位在前”也不是不行但进位时就得在头部插入效率低代码也更别扭。我见过不少新手写反存储方向导致加减乘除四个函数全部出 bug排查起来非常痛苦。2.2 字符串输入与数组转换大数只能用字符串读入因为没有任何整型能装下几千位的数字。转换过程很简单从字符串末尾往前遍历每次 s[i] - 0 得到对应数字push 进数组。这里有一个容易出错的细节输入字符串可能带前导零比如 “00123”。如果直接转换数组里会多出两个 0后续计算没问题但输出时就会出现前面多打印零的情况。更严谨的做法是转换后调用一个去除前导零的函数。#include bits/stdc.h using namespace std; // 去除前导零保证数组至少保留一位 void trim(vectorint a) { while (a.size() 1 a.back() 0) a.pop_back(); } // 字符串转高精度数组低位在前 vectorint str2num(const string s) { vectorint a; for (int i (int)s.size() - 1; i 0; --i) { a.push_back(s[i] - 0); } trim(a); return a; } // 比较两个非负大数的大小 // 返回 1 表示 ab0 表示相等-1 表示 ab int cmp(const vectorint a, const vectorint b) { if (a.size() ! b.size()) { return a.size() b.size() ? 1 : -1; } for (int i (int)a.size() - 1; i 0; --i) { if (a[i] ! b[i]) return a[i] b[i] ? 1 : -1; } return 0; }trim 函数必须注意一个边界如果数字是 0数组是 {0}不能把最后一个 0 也去掉。所以 while 条件是 size() 1至少保留一位。2.3 压位用空间换时间的实用技巧基础模板用十进制每一位存一个 0 到 9 的数字直观但浪费空间。举个例子计算 10000!结果大约有 38660 位你要处理四万次循环。如果压位把每 4 位数字打包成一个 int 存储数组长度直接缩小到原来的四分之一运算循环次数也大幅降低。压位的做法是设置 BASE 10000比如数字 123456789在万进制下表示为 {6789, 2345, 1}因为从低位开始每 4 位一组6789、2345、1。压位后的加减乘除逻辑和十进制完全一样只是进位和借位的界限从 10 变成了 10000。但有一个关键坑乘法累加时c[ij] 可能累积相当大的值。如果 BASE 取 10000一位乘以一位最大是 9999×9999 ≈ 10^8累加几千次就超过 int 范围。所以压位乘法时c 数组要么用 long long 存储要么在每步取模时小心处理。我习惯 BASE 取 10000配合 long long 做进位稳当且性能足够。压位后的输出也和普通不同不能直接逐个数字打印。因为数组里每个元素代表 4 位最高位那段可能不足 4 位直接打印没问题但中间的段如果不足 4 位必须补前导零否则数字就“变短”了。正确做法是先打印最高位其余位用 printf(%04d) 补零。const int BASE 10000; void printPacked(const vectorint a) { printf(%d, a.back()); for (int i (int)a.size() - 2; i 0; --i) { printf(%04d, a[i]); } printf(\n); }压位模板我建议在备赛后期再掌握先把十进制模板练熟。因为本质上两者只是 BASE 不同进位逻辑一模一样。如果你连十进制都写不溜贸然压位只会增加调试难度。3. 实战模板高精度四则运算核心代码3.1 加法模拟竖式记得最后进位加法是最简单的高精度运算。从最低位开始逐位相加加上进位结果对 10 取余作为当前位除以 10 作为新的进位。循环结束后如果进位还有值别忘补到最高位。vectorint add(const vectorint a, const vectorint b) { vectorint c; int carry 0; int n max(a.size(), b.size()); for (int i 0; i n; i) { if (i (int)a.size()) carry a[i]; if (i (int)b.size()) carry b[i]; c.push_back(carry % 10); carry / 10; } if (carry) c.push_back(carry); return c; }这个模板不需要先对较短的数组补零直接在循环里通过 i a.size() 判断简洁不容易错。一个小测试999 1循环三次carry 依次是 10、10、10每一位都是 0最后 carry1 补进最高位结果得到 1000完美。3.2 减法先比较大小再借位减法的核心难点是处理负数和借位。我的建议是自己实现的减法函数默认要求 a b也就是只做非负数的减法返回 a - b 的绝对值。调用前先用 cmp 函数判断大小如果 a b就交换参数并标记结果为负数。借位逻辑当前位是 a[i] - 借位如果 i b.size() 还要再减去 b[i]。如果结果小于 0就加 10 并向高位借 1否则借位清零。// 要求 a b调用前用 cmp 判断 vectorint sub(const vectorint a, const vectorint b) { vectorint c; int borrow 0; for (int i 0; i (int)a.size(); i) { int cur a[i] - borrow; if (i (int)b.size()) cur - b[i]; if (cur 0) { cur 10; borrow 1; } else { borrow 0; } c.push_back(cur); } trim(c); // 去掉前导零但如果结果是 0保留一位 0 return c; }有人会问如果 a b结果是 0trim 之后数组变成 {0}完全正确。但如果 a b 且从最高位一直借位到结束循环结束时 borrow 理论上一定是 0因为这是 a b 的前提保证。如果调用前没做大小判断这里就会出现 borrow 为 1 的诡异情况结果变成负数但数组只存了绝对值所以在外面把好关很关键。3.3 乘法双重循环与集中进位高精度乘法也是模拟竖式但不是逐位动态进位而是先做一个“[卷积]”式的累加再统一进位。这里我用了一个小技巧先不管进位把每一位的乘积累加到 c[ij] 中所有乘累加结束后再从低位到高位集中处理进位。vectorint mul(const vectorint a, const vectorint b) { vectorint c(a.size() b.size(), 0); for (int i 0; i (int)a.size(); i) { for (int j 0; j (int)b.size(); j) { c[i j] a[i] * b[j]; } } // 集中进位 for (int i 0; i (int)c.size() - 1; i) { c[i 1] c[i] / 10; c[i] % 10; } trim(c); return c; }为什么用这种“先累加后进位”的方式因为如果把进位放在内层循环里每加一次就要取模一次代码更繁琐而集中进位的循环次数是 O(n m)即使累加值比较大也能一次性处理干净。实际比赛里高精度乘高精度的场景没有想象中那么多。更多时候是一个高精度数乘以一个普通 int比如阶乘。这时候写一个 mulSmall 函数配合单次进位效率高得多。vectorint mulSmall(const vectorint a, int b) { if (b 0) return vectorint{0}; vectorint c; int carry 0; for (int i 0; i (int)a.size(); i) { carry a[i] * b; c.push_back(carry % 10); carry / 10; } while (carry) { c.push_back(carry % 10); carry / 10; } trim(c); return c; }mulSmall 的进位逻辑是当前位的结果是 a[i] * b 加上之前的进位对 10 取余留下当前位除以 10 进入下一轮。循环结束后进位可能不止一位用 while 一直往高位推。3.4 除法除以单精度与大数除以大数除法是高精度运算里最容易劝退人的部分。我分两个难度来讲。高精度除以单精度int 除以 int 的除数比较简单直接从最高位开始模拟长除法当前余数乘 10加上当前位数字除以除数得到商的一位取余作为新的余数。// 高精度 a 除以普通整数 b商返回余数通过 r 带回 vectorint divSingle(const vectorint a, int b, int r) { vectorint c(a.size(), 0); r 0; for (int i (int)a.size() - 1; i 0; --i) { r r * 10 a[i]; c[i] r / b; r % b; } trim(c); return c; }注意这里的循环是从数组末尾向开头遍历也就是从数字的最高位向最低位处理。因为除法的竖式是从高位开始的和加减乘正好相反。如果这里反了结果完全错误。高精度除以高精度就复杂了蓝桥杯现场如果没有现成模板我建议直接采用“逐位试商”的方法从被除数的最高位开始每轮把当前位“补”到余数后面然后从 9 到 0 依次试探找到最大的 k 满足 k × b ≤ 当前余数。把 k 写入商用当前余数减去 k × b 得到新的余数。本质上就是小学长除法只不过每一步的乘法和减法都用高精度实现。vectorint divBig(const vectorint a, const vectorint b) { vectorint q; // 商暂存高位到低位 vectorint rem; // 余数 for (int i (int)a.size() - 1; i 0; --i) { // rem rem * 10 a[i]相当于在数字右侧补上一位 rem.insert(rem.begin(), a[i]); trim(rem); int k 0; vectorint prod; // 从 9 到 1 试商 for (int d 9; d 1; --d) { prod mulSmall(b, d); if (cmp(prod, rem) 0) { k d; break; } } if (k) rem sub(rem, prod); q.push_back(k); } reverse(q.begin(), q.end()); trim(q); return q; }这个模板有一个前提调用前要判断 b 不为 0。另外它的时间复杂度是 O(n × 9 × m)对于长度几千位的数字来说蓝桥杯的数据范围完全够用。如果被除数和除数都上万位就需要更高级的优化了但那种题在蓝桥杯里基本不会出现。3.5 负数怎么处理很多选手写高精度只考虑非负数遇到负数就懵。我的处理方式很简单用一个 bool 变量记录符号vector 只存绝对值。四则运算时按符号分类加法同号则绝对值相加异号则比较绝对值大小大减小符号取绝对值大的一方。减法a - b 等价于 a (-b)把减法统一到加法的逻辑上。比较大小先看符号负数小于非负数同符号时再比较绝对值。比赛里真正要求你处理负数的场景比较少但“求差”这类题经常出现所以至少要把“先比大小再决定正负”这个逻辑写好。我在本地模板里会额外写一个 signedAdd 和 signedSub 的封装直接用 bool sign 存储符号避免每次都在主逻辑里手写判断。4. 典型场景还原蓝桥杯高频题型与实战思路4.1 大数阶乘与阶乘和大数阶乘是蓝桥杯的高频考点比如要求输出 n! 的所有位n 可以到 1000 甚至 10000。直接用 mulSmall 从 1 乘到 n 就行每乘一个 i就是在原有高精度结果上乘以一个普通整数完全不需要高精度乘高精度。vectorint factorial(int n) { vectorint res{1}; for (int i 2; i n; i) { res mulSmall(res, i); } return res; }求阶乘和1! 2! ... n!更常见如果对每个 k 单独调用 factorial(k)复杂度是 O(n²)虽然数据范围不大时也能跑但没必要。更好的做法是递推维护当前阶乘 cur每次 cur mulSmall(cur, i)然后 sum add(sum, cur)。这样只需要一次高精度乘法和加法循环快得多。4.2 大数幂运算有些题要求输出 2^n 的完整值n 可能到几百甚至几千。不要一上来就写高精度乘高精度的快速幂因为 2^1000 只有 302 位直接循环乘 2 一千次完全没问题。但如果 n 是几百万循环乘 2 就太慢了。这时候可以考虑按位数估算如果结果位数超过几万单纯的循环乘法会越来越慢因为位数线性增长总复杂度是 O(n²)。这种情况下用快速幂配合高精度乘高精度mul 函数是更好的选择快速幂的乘法次数只有 O(log n)。不过我要提醒一点蓝桥杯的数据范围往往经过设计如果你发现乘 2 的循环次数高达十万、百万那大概率题目有别的技巧比如只输出模意义下的结果或者末几位而不是让你暴力算完整个大数。4.3 大组合数精确值组合数 C(n, k) 的精确值经常出现在概率、方案数的题目中。当 n、k 很大时long long 根本装不下。精确计算组合数有一个常用递推公式C(n, k) C(n, k-1) × (n - k 1) / k翻译成高精度操作就是用 mulSmall 乘以 (n - k 1)再用 divSingle 除以 k。因为递推过程中每一步的结果都能被 k 整除所以不用担心小数。// 返回 C(n, k) 的精确值要求 0 k n vectorint combination(int n, int k) { if (k n - k) k n - k; vectorint res{1}; for (int i 1; i k; i) { res mulSmall(res, n - k i); int r; res divSingle(res, i, r); } return res; }这个模板在我的备赛笔记里出现过很多次解决了好几道组合计数题。4.4 高精度小数的特殊情况严格来说“小数高精度”在蓝桥杯很少单独出现但偶尔会碰到需要高精度计算到小数点后若干位的题。我的处理思路是把所有数字统一放大成整数来处理比如保留 6 位小数就把所有数值乘 10^6最后输出时在正确位置补小数点。这样就能复用整数高精度的加减乘除模板不需要另写一套。这种“定点数”思路本质上是把浮点问题转化为整数问题避开浮点误差。如果你遇到乘法注意放大倍数会平方增长比如保留 6 位小数的两个数相乘结果放大倍数是 10^12最后要缩小回去别搞混。5. 调试、避坑与现场保分策略5.1 三个我踩过的低级错误第一个错误是字符串转数组时下标顺序搞反。刚开始写 str2num有人会顺手写成 for (int i 0; i s.size(); i) a.push_back(s[i] - 0)读字符串 “123” 变成数组 {1,2,3}即数字 321后面所有运算全乱。我建议在 str2num 里写一行注释低位在前切记。第二个错误是减法结果忘记处理前导零。10 - 9 1但如果你的数组是 {0, 1}不 trim 的话输出就变成 01。尤其当结果为 0 时数组会变成 {0, 0, 0 ...}一 trim 又把全部零去掉数组变成空。所以 trim 的终止条件是 size() 1不是 size() 0。第三个错误是压位输出时没有补零。BASE10000 压位后数组 {1, 2, 3} 表示的数字是 3×10000² 2×10000 1 300020001但如果最高位后面的段不补零直接打印就变成 3121相差十万八千里。这是压位模板最容易翻车的地方。5.2 边界数据与评测点高精度模板写完后千万别直接交。我习惯在本地跑一组固定测试用例999 1检验加法最高位进位。1000 - 1检验减法借位链。999 × 999检验乘法进位集中处理。123456789 / 12345对比 Python 计算结果检验除法。0 0、0 - 0、0 × 999检验全零边界。这些用例几乎覆盖了评测系统最容易埋的边界陷阱。只要这几个都能通过再大的数字基本也不会出问题。5.3 怎么用对拍验证模板更严谨的验证方式是对拍用 Python 写一个用原生大整数计算结果的小脚本生成随机测试数据再用你的 C 高精度程序算一遍逐项比对输出。对拍脚本不需要多复杂核心三步Python 随机生成两个大数和运算符。分别调用 Python 内置运算得出正确答案以及你编译好的 C 程序得出待测答案。逐行比较一旦不一致立刻输出测试数据和两个答案。这个方法能帮你在赛前发现模板里隐藏的 bug强烈建议每个人都在备赛时做一次。我用这个方法至少揪出了三次隐藏的边界错误都是靠手测很难发现的。5.4 考场上写不出高精度除法怎么办最后说一个很现实的保分策略高精度除法尤其是高精度除以高精度是整套模板里最复杂、最容易写错的部分。如果比赛现场发现时间不够不要慌分情况处理。如果题目只需要商和余数中的一种并且除数也是大数优先检查有没有可能用“高精度除以单精度”特判部分数据比如数据范围有 30% 的小数据先把这部分分拿稳。如果是求精确结果采用逐位试商法代码量其实不大关键是平时练熟。还有一个取巧的办法有些题目求两个大数的整除结果可以利用二分答案。二分商 q每次用 mul(b, q) 判断 q×b 是否 ≤ a。这种做法跑得比逐位试商慢但胜在逻辑简单、不容易写错用来拿部分分或者应对不常见的数据范围绰绰有余。我个人备赛时的习惯是把高精度整套模板放在代码库的固定位置每次模拟赛前先默写一遍加法和乘法再顺手写减法、除法。默写几次之后考场上根本不需要想手指比脑子快。真正理解了竖式原理之后你会发现高精度没有想象中那么可怕它就是一个稍微繁琐一点的模拟题。把这些模板练成条件反射蓝桥杯的大数题对你来说就是送分题。
