打开你的Java IDE新建一个类写上import java.math.BigInteger;然后开始刷高精度题。这一套动作备考蓝桥杯Java组的同学应该都不陌生。今天是我们备战系列的第10天主题就是高精度。高精度在蓝桥杯里算不上最冷门但也绝不是每年必考的大热点。它更像一个“隐藏关卡”——一旦题目里出现了超出long范围的大数或者要求计算阶乘、幂次、大数加减乘除没准备的人当场卡壳准备过的人五分钟写完。更关键的是高精度还经常和贪心、动态规划、数论组合在一起比如“大数斐波那契”“大数卡特兰数”你以为在考算法其实卡在了大数存储上。这篇博文不打算讲那种“高精度就是模板背一背”的套路而是想站在一个真实备赛者的角度带你搞清楚三件事第一蓝桥杯里的高精度到底喜欢怎么考第二Java内置的BigInteger和BigDecimal够不够用、怎么用才稳第三什么时候必须手写高精度手写模板怎么才不容易写崩。无论你是刚开始刷题的萌新还是已经在真题里被大数折磨过的老手这篇都能给你一些实在的东西。1. 高精度到底在考什么1.1 核心考法大数运算的三种出现方式高精度题的题干通常不会直接说“请用高精度”而是用数据范围暗示你。比如n 1000要你求n!或者a和b最大有1000位让你算两数之和。这种题背后其实就是大数运算。我自己的经验是蓝桥杯里的高精度主要藏在三种考法里纯高精度应用题输入两个超长整数做加减乘除或者求幂。这类题最直白考的就是模板熟不熟。比如“高精度加法”“高精度减法”“高精度乘法”PTA上这类题目的分数都不低很多学校也拿它当Java课的作业题。高精度作为中间步骤算法本身不复杂但计算过程中会产生很大的数。典型的就是递推求斐波那契数列的第n项n到500甚至1000或者动态规划里状态值是超大整数。这时候如果不会处理大数整个题的思路都是对的代码却跑不出结果。高精度配合数论/组合数学比如卡特兰数、斯特林数、大组合数取模之前的原始值或者2^1000这种经典题目。这类题在国赛和省赛的填空题、大题里都出现过。所以高精度不是一个孤立的知识点它是你算法工具箱里的基础设施。我现在刷题时有个习惯看到数据范围里有“大数”“长整数”“1000位”这些敏感词第一反应就是“这题大概率要处理大数”。1.2 为什么Java组依然要学手写高精度聊到这儿肯定有同学会问Java不是有BigInteger吗直接new BigInteger(123456789)不就行了为什么还要学手写这个问题的答案我在备赛初期也困惑了很久。BigInteger确实能处理任意大的整数内部用数组模拟了大数运算正常比赛用它完全没问题。但问题在于比赛题目有时候不是在考你“会不会调用库”而是在考你“懂不懂原理”。比如填空题让你写结果你当然可以用BigInteger算出来但有些题目要求你输出过程、拼接字符串、在递归里反复进行大数运算BigInteger虽然能跑性能却不一定扛得住。更关键的是手写高精度能帮你建立对大数运算的直觉——你知道了进位、借位、乘法错位相加的过程遇到需要用数组模拟状态、需要自定义大数结构去配合记忆化搜索的时候才不会一头雾水。我个人的建议是以BigInteger为主手写模板为辅。在正式比赛里只要能调用库就调用库省时省力还不出错但在平时练习时至少要把加法和乘法的原理手推一遍并且准备一套自己的手写模板以备不时之需。2. Java自带的高精度类BigInteger与BigDecimal2.1 BigInteger的常用API与踩坑记录BigInteger是Java里处理任意精度整数的主力类。它的构造方式有几种平时最常用的是通过字符串构造BigInteger a new BigInteger(12345678901234567890); BigInteger b BigInteger.valueOf(100); // 从long转换核心运算方法就那么几个add、subtract、multiply、divide、mod、pow、gcd以及比较用的compareTo。写的时候注意BigInteger是不可变对象每一次运算都会返回新的对象不会修改原值BigInteger a new BigInteger(100); BigInteger b new BigInteger(20); BigInteger sum a.add(b); // 120 BigInteger diff a.subtract(b); // 80 BigInteger prod a.multiply(b); // 2000 BigInteger quot a.divide(b); // 5 BigInteger rem a.mod(b); // 0这里有几个我实际踩过的坑不要用比较BigInteger。比较的是引用地址即使数值相同也可能返回false。要比较大小用a.compareTo(b) 0来判断相等用a.compareTo(b) 0判断大于。除法要注意整除和取模。如果两个整数不能整除divide会直接丢弃小数部分而不是四舍五入。想保留余数就再用mod或者直接调用divideAndRemainder一次拿数组。pow方法的指数参数是int不是BigInteger。所以BigInteger.valueOf(2).pow(1000)没问题但指数特别大时需要自己写快速幂。new BigInteger(0)是可以的但不要写new BigInteger(0)那个构造函数的参数是bit长度不是数值。还有一个经常被忽略的是进制转换。蓝桥杯偶尔会有“进制转换”相关的题BigInteger可以轻松搞定BigInteger value new BigInteger(FF, 16); // 从16进制字符串构造 String hex value.toString(16); // 转回16进制 String bin value.toString(2); // 转成2进制这个功能在题目要求“将一个大数十进制转二进制”时能省下大量手写转换的代码。2.2 BigDecimal的精度陷阱BigDecimal是用来处理高精度小数的在蓝桥杯里出现频率没有BigInteger高但一旦出现坑往往比较隐蔽。最典型的问题就是构造时的精度丢失。BigDecimal a new BigDecimal(0.1); // 不推荐会有误差 BigDecimal b new BigDecimal(0.1); // 推荐用字符串构造new BigDecimal(0.1)传入的是double而double本身对0.1的存储就不精确所以构造出来的BigDecimal也是不精确的。关键原则能用字符串构造就不要用double构造。除法的精度问题也很常见。BigDecimal做除法时如果除不尽会抛ArithmeticException必须指定精度和舍入模式BigDecimal a new BigDecimal(1); BigDecimal b new BigDecimal(3); BigDecimal result a.divide(b, 10, RoundingMode.HALF_UP); // 保留10位四舍五入蓝桥杯里遇到“保留几位小数”的题我会直接套这个模板避免在线评测系统报Non-terminating decimal expansion错误。2.3 性能对比与备赛策略单从代码量看BigInteger赢麻了。但从性能看BigInteger在超大数乘法上并不占优——尤其是两个上万位的数相乘时内部实现的复杂度比你手写的O(n^2)模拟并没有质的提升它内部用了更复杂的Karatsuba算法但整体上仍是高阶复杂度。不过在蓝桥杯的数据范围里BigInteger完全够用。所以我的备赛策略是三层第一层最优先熟悉BigInteger、BigDecimal的常用API会处理常见异常。比赛时能用库就用库。第二层准备自己手写的高精度加减乘法模板确保在没有BigInteger的环境下也不慌。第三层理解大数运算的原理尤其是“数组模拟手算”的过程这样碰到需要大数参与递推的题时你能自己设计数据结构。三层都过了高精度这块基本就稳了。3. 手写高精度模板从原理到代码3.1 数组模拟的核心思想模拟手算如果不用BigInteger最经典的高精度做法是用数组或字符串来模拟手算。这个思路说起来很简单我们小时候列竖式算加法就是一位一位对齐相加逢十进一。代码也是这么做。常见的存储方式有两种一种是从低位到高位存数组另一种是直接从字符串高位开始处理。我更推荐第一种因为处理进位和借位时下标从0开始非常方便。比如数字12345用int[] a存储时倒过来存就是a[0] 5; // 个位 a[1] 4; // 十位 a[2] 3; a[3] 2; a[4] 1; // 万位为什么要倒着存因为加法要做进位如果正着存个位下标是len - 1进位时下标变小处理起来绕来绕去。倒着存之后每一位的进位都往i 1方向推思路清晰很多。3.2 高精度加法模板与细节加法模板大概是这样的public static String add(String s1, String s2) { int[] a new int[s1.length()]; int[] b new int[s2.length()]; for (int i 0; i s1.length(); i) { a[i] s1.charAt(s1.length() - 1 - i) - 0; } for (int i 0; i s2.length(); i) { b[i] s2.charAt(s2.length() - 1 - i) - 0; } int len Math.max(s1.length(), s2.length()) 1; int[] c new int[len]; for (int i 0; i len; i) { if (i a.length) c[i] a[i]; if (i b.length) c[i] b[i]; c[i 1] c[i] / 10; // 进位 c[i] % 10; } // 去掉前导零并转为字符串 StringBuilder sb new StringBuilder(); int idx len - 1; while (idx 0 c[idx] 0) idx--; for (int i idx; i 0; i--) { sb.append(c[i]); } return sb.toString(); }这个模板里的关键是c[i 1] c[i] / 10这行。它模拟的就是“逢十进一”。如果你在比赛里手写最容易写错的地方就是进位的处理顺序一定要先算进位再取模否则进位就丢了。还有一个小细节结果数组长度要设置成Math.max(len1, len2) 1多出的那一位是为了存最高位的进位。比如999 1 1000最高位需要多一位才能放下。3.3 高精度减法借位才是灵魂减法比加法麻烦一点因为要处理“谁大谁小”和“借位”。我通常先写一个比较函数判断两个数的大小保证用大的减小的最后根据符号决定是否输出负号。public static String subtract(String s1, String s2) { boolean negative false; // 如果s1 s2则结果加负号并交换两个数 if (s1.length() s2.length() || (s1.length() s2.length() s1.compareTo(s2) 0)) { String tmp s1; s1 s2; s2 tmp; negative true; } int[] a new int[s1.length()]; int[] b new int[s2.length()]; for (int i 0; i s1.length(); i) { a[i] s1.charAt(s1.length() - 1 - i) - 0; } for (int i 0; i s2.length(); i) { b[i] s2.charAt(s2.length() - 1 - i) - 0; } int[] c new int[s1.length()]; for (int i 0; i s1.length(); i) { c[i] a[i]; if (i b.length) c[i] - b[i]; if (c[i] 0) { c[i] 10; int j i 1; // 借位从下一位借1如果下一位是0继续往后借 while (j s1.length() c[j] 0) { c[j] 9; j; } c[j]--; } } StringBuilder sb new StringBuilder(); int idx s1.length() - 1; while (idx 0 c[idx] 0) idx--; for (int i idx; i 0; i--) { sb.append(c[i]); } if (negative) { sb.insert(0, -); } return sb.toString(); }减法模板的借位逻辑很容易写乱特别是1024 - 999这种情况中间会连续借位。上面的写法是“向后找第一个非零位借1之后中间经过的0全部变成9”这个思路完全模拟了手算习惯之后就不容易错。不过说句实在话在正式比赛里我几乎不会手写减法模板因为有BigInteger.subtract。我写这个模板的主要目的是确保自己“真的懂”借位过程防止哪天题目环境特殊比如某些在线评测系统不让用BigInteger时手足无措。3.4 高精度乘法错位相加不迷路乘法比加减法更考验编码功底。核心思路是a的第i位和b的第j位相乘结果加到c[i j]上。这个i j就是所谓的“错位”。public static String multiply(String s1, String s2) { int n s1.length(), m s2.length(); int[] a new int[n]; int[] b new int[m]; for (int i 0; i n; i) a[i] s1.charAt(n - 1 - i) - 0; for (int i 0; i m; i) b[i] s2.charAt(m - 1 - i) - 0; int[] c new int[n m]; for (int i 0; i n; i) { for (int j 0; j m; j) { c[i j] a[i] * b[j]; } } // 统一处理进位 for (int i 0; i n m - 1; i) { c[i 1] c[i] / 10; c[i] % 10; } StringBuilder sb new StringBuilder(); int idx n m - 1; while (idx 0 c[idx] 0) idx--; for (int i idx; i 0; i--) { sb.append(c[i]); } return sb.toString(); }这个模板的精妙之处在于它没有在双重循环内部处理进位而是先让c[i j]累加所有乘积最后再统一进位。这样做的好处是逻辑简单不容易出错。代价是c[i]可能暂时超过10但int完全扛得住。注意一个细节两个长度分别为n和m的数相乘结果位数最多是n m所以数组开n m是足够的。4. 蓝桥杯高频题型与真题拆解4.1 典型真题大数加法变形题蓝桥杯的纯高精度题不会太难但会“包装”。比如给你一个很大的数字符串形式要求你求它加1之后的结果或者判断它是不是回文数。这里有一个关键点输入可能是几百位的字符串直接转long会溢出必须按字符串或BigInteger处理。我之前看到一个很典型的例子“1-9 高精度减法(subtraction) 分数10 作者 jackson 单位 上海大学”这是很多学校Java课程的经典大作业题要求计算两个大整数之差。题目描述非常简单但恰恰能考出你对字符串处理、借位逻辑、负数判断的掌握程度。这种题我建议你先用BigInteger写一版快速通过的代码再用手写模板实现一遍对比两种写法的代码量和出错率感受一下差距。我自己这么练过之后最大的收获是明白了“库函数节省的不仅是时间还有心智负担”。但也知道了“在某些特殊场景下手写模板能帮我把数据结构和算法思想打通”。4.2 高精度递推斐波那契与卡特兰数蓝桥杯考高精度经常是把它嵌在递推题里。比如求斐波那契数列的第n项n到了1000以上结果已经远超long范围这时候你就必须在递推里用大数。如果使用BigInteger代码很直接BigInteger[] fib new BigInteger[n 1]; fib[0] BigInteger.ZERO; fib[1] BigInteger.ONE; for (int i 2; i n; i) { fib[i] fib[i - 1].add(fib[i - 2]); }这种题对于会BigInteger的人来说就是送分题。但问题是有些递归写法会超时因为你重复计算了大量子问题。此时就算你用了BigInteger也没用因为性能瓶颈在算法层面。所以遇到这种题正确的解题姿势是先优化算法比如记忆化、滚动变量再套用大数类型。卡特兰数也是一样的道理。递推式C(n1) C(n) * (4n 2) / (n 2)里既有乘法又有除法用BigInteger做除法时要特别小心因为BigInteger的整数除法会截断小数。好在卡特兰数本身一定是整数用divide不会出问题前提是你算的过程中不要有精度丢失。4.3 大数阶乘的两种写法对比求n!是蓝桥杯里非常经典的高精度题目n到1000时结果已经是天文数字。用BigInteger写代码非常优雅BigInteger res BigInteger.ONE; for (int i 2; i n; i) { res res.multiply(BigInteger.valueOf(i)); }这段代码的时间复杂度是O(n * 大数乘法复杂度)在n 1000的时候一点问题都没有。但如果你想追求极致的效率可以改成“分段乘”或者用数组手写累乘不过这属于竞赛优化范畴备赛初期不需要太纠结。我在备赛时专门对比过同一个n500的阶乘BigInteger版本写起来不到一分钟手写数组模拟要用Classic模板反复调代码量翻倍运行时间反而没有显著优势。因此在蓝桥杯这种“求稳大于炫技”的比赛中我强烈建议你用BigInteger。5. 备赛调试避坑清单5.1 前导零与字符串输出无论你是用BigInteger还是手写模板输出的时候都要注意前导零。BigInteger的toString已经帮你处理好了但手写模板需要自己处理。我在模板里写的while (idx 0 c[idx] 0) idx--;就是为了跳过高位多余的0。如果不处理123 0可能会输出0123直接WA。5.2 负数与符号处理大数减法里最容易翻车的是负数。如果你用BigInteger直接subtract就完事了符号自动处理。如果你手写一定要先比较大小。我自己的习惯是只要题目没有特别限制优先用BigInteger因为它对符号、零、负数的处理非常完善我不用在细节上反复测试。5.3 性能瓶颈与超时排查用BigInteger超时的情况我遇到过两次一次是循环次数太多一次是没做预处理。排查思路很简单先看算法是不是有重复计算比如递归里反复new BigInteger。再看不必要的大数运算能不能用long替代比如某些中间量虽然最终结果很大但中间过程很小可以先算long再转BigInteger。最后看能不能用快速幂替代普通循环里的连乘。5.4 输入输出的配合技巧蓝桥杯的在线评测系统对输入输出的稳定性要求很高。大数输入通常是用String接收然后转成BigInteger输出直接System.out.println。如果你的程序要输出几千位的数println完全没问题不要手动拼字符串再输出那样反而容易错。另外如果你用BigDecimal处理浮点大数输出时注意去掉末尾多余的0可以用stripTrailingZeros()方法。蓝桥杯有时候会要求“输出整数部分”你直接.toBigInteger()转换就行。聊到这儿高精度这块就算梳理得差不多了。我个人在实际备赛中的体会是高精度题从来不是蓝桥杯的难点核心但它是那种“会了就稳拿不会就干瞪眼”的知识点。你不需要把每个手写模板都背得滚瓜烂熟但一定要知道原理知道什么时候用BigInteger什么时候必须自己模拟。最后再分享一个小技巧刷高精度题的时候建议你每次都用两种方式各写一遍——先BigInteger快速AC再手写模拟一遍。这样既能保证比赛时的正确率又能让你真正理解大数运算的本质。等你练熟了看到“1000位整数求和”这类题第一反应就不会是“这怎么算”而是“一行add搞定”。这种游刃有余的状态就是Day10最大的收获。
蓝桥杯Java备赛：高精度运算与BigInteger实战指南
打开你的Java IDE新建一个类写上import java.math.BigInteger;然后开始刷高精度题。这一套动作备考蓝桥杯Java组的同学应该都不陌生。今天是我们备战系列的第10天主题就是高精度。高精度在蓝桥杯里算不上最冷门但也绝不是每年必考的大热点。它更像一个“隐藏关卡”——一旦题目里出现了超出long范围的大数或者要求计算阶乘、幂次、大数加减乘除没准备的人当场卡壳准备过的人五分钟写完。更关键的是高精度还经常和贪心、动态规划、数论组合在一起比如“大数斐波那契”“大数卡特兰数”你以为在考算法其实卡在了大数存储上。这篇博文不打算讲那种“高精度就是模板背一背”的套路而是想站在一个真实备赛者的角度带你搞清楚三件事第一蓝桥杯里的高精度到底喜欢怎么考第二Java内置的BigInteger和BigDecimal够不够用、怎么用才稳第三什么时候必须手写高精度手写模板怎么才不容易写崩。无论你是刚开始刷题的萌新还是已经在真题里被大数折磨过的老手这篇都能给你一些实在的东西。1. 高精度到底在考什么1.1 核心考法大数运算的三种出现方式高精度题的题干通常不会直接说“请用高精度”而是用数据范围暗示你。比如n 1000要你求n!或者a和b最大有1000位让你算两数之和。这种题背后其实就是大数运算。我自己的经验是蓝桥杯里的高精度主要藏在三种考法里纯高精度应用题输入两个超长整数做加减乘除或者求幂。这类题最直白考的就是模板熟不熟。比如“高精度加法”“高精度减法”“高精度乘法”PTA上这类题目的分数都不低很多学校也拿它当Java课的作业题。高精度作为中间步骤算法本身不复杂但计算过程中会产生很大的数。典型的就是递推求斐波那契数列的第n项n到500甚至1000或者动态规划里状态值是超大整数。这时候如果不会处理大数整个题的思路都是对的代码却跑不出结果。高精度配合数论/组合数学比如卡特兰数、斯特林数、大组合数取模之前的原始值或者2^1000这种经典题目。这类题在国赛和省赛的填空题、大题里都出现过。所以高精度不是一个孤立的知识点它是你算法工具箱里的基础设施。我现在刷题时有个习惯看到数据范围里有“大数”“长整数”“1000位”这些敏感词第一反应就是“这题大概率要处理大数”。1.2 为什么Java组依然要学手写高精度聊到这儿肯定有同学会问Java不是有BigInteger吗直接new BigInteger(123456789)不就行了为什么还要学手写这个问题的答案我在备赛初期也困惑了很久。BigInteger确实能处理任意大的整数内部用数组模拟了大数运算正常比赛用它完全没问题。但问题在于比赛题目有时候不是在考你“会不会调用库”而是在考你“懂不懂原理”。比如填空题让你写结果你当然可以用BigInteger算出来但有些题目要求你输出过程、拼接字符串、在递归里反复进行大数运算BigInteger虽然能跑性能却不一定扛得住。更关键的是手写高精度能帮你建立对大数运算的直觉——你知道了进位、借位、乘法错位相加的过程遇到需要用数组模拟状态、需要自定义大数结构去配合记忆化搜索的时候才不会一头雾水。我个人的建议是以BigInteger为主手写模板为辅。在正式比赛里只要能调用库就调用库省时省力还不出错但在平时练习时至少要把加法和乘法的原理手推一遍并且准备一套自己的手写模板以备不时之需。2. Java自带的高精度类BigInteger与BigDecimal2.1 BigInteger的常用API与踩坑记录BigInteger是Java里处理任意精度整数的主力类。它的构造方式有几种平时最常用的是通过字符串构造BigInteger a new BigInteger(12345678901234567890); BigInteger b BigInteger.valueOf(100); // 从long转换核心运算方法就那么几个add、subtract、multiply、divide、mod、pow、gcd以及比较用的compareTo。写的时候注意BigInteger是不可变对象每一次运算都会返回新的对象不会修改原值BigInteger a new BigInteger(100); BigInteger b new BigInteger(20); BigInteger sum a.add(b); // 120 BigInteger diff a.subtract(b); // 80 BigInteger prod a.multiply(b); // 2000 BigInteger quot a.divide(b); // 5 BigInteger rem a.mod(b); // 0这里有几个我实际踩过的坑不要用比较BigInteger。比较的是引用地址即使数值相同也可能返回false。要比较大小用a.compareTo(b) 0来判断相等用a.compareTo(b) 0判断大于。除法要注意整除和取模。如果两个整数不能整除divide会直接丢弃小数部分而不是四舍五入。想保留余数就再用mod或者直接调用divideAndRemainder一次拿数组。pow方法的指数参数是int不是BigInteger。所以BigInteger.valueOf(2).pow(1000)没问题但指数特别大时需要自己写快速幂。new BigInteger(0)是可以的但不要写new BigInteger(0)那个构造函数的参数是bit长度不是数值。还有一个经常被忽略的是进制转换。蓝桥杯偶尔会有“进制转换”相关的题BigInteger可以轻松搞定BigInteger value new BigInteger(FF, 16); // 从16进制字符串构造 String hex value.toString(16); // 转回16进制 String bin value.toString(2); // 转成2进制这个功能在题目要求“将一个大数十进制转二进制”时能省下大量手写转换的代码。2.2 BigDecimal的精度陷阱BigDecimal是用来处理高精度小数的在蓝桥杯里出现频率没有BigInteger高但一旦出现坑往往比较隐蔽。最典型的问题就是构造时的精度丢失。BigDecimal a new BigDecimal(0.1); // 不推荐会有误差 BigDecimal b new BigDecimal(0.1); // 推荐用字符串构造new BigDecimal(0.1)传入的是double而double本身对0.1的存储就不精确所以构造出来的BigDecimal也是不精确的。关键原则能用字符串构造就不要用double构造。除法的精度问题也很常见。BigDecimal做除法时如果除不尽会抛ArithmeticException必须指定精度和舍入模式BigDecimal a new BigDecimal(1); BigDecimal b new BigDecimal(3); BigDecimal result a.divide(b, 10, RoundingMode.HALF_UP); // 保留10位四舍五入蓝桥杯里遇到“保留几位小数”的题我会直接套这个模板避免在线评测系统报Non-terminating decimal expansion错误。2.3 性能对比与备赛策略单从代码量看BigInteger赢麻了。但从性能看BigInteger在超大数乘法上并不占优——尤其是两个上万位的数相乘时内部实现的复杂度比你手写的O(n^2)模拟并没有质的提升它内部用了更复杂的Karatsuba算法但整体上仍是高阶复杂度。不过在蓝桥杯的数据范围里BigInteger完全够用。所以我的备赛策略是三层第一层最优先熟悉BigInteger、BigDecimal的常用API会处理常见异常。比赛时能用库就用库。第二层准备自己手写的高精度加减乘法模板确保在没有BigInteger的环境下也不慌。第三层理解大数运算的原理尤其是“数组模拟手算”的过程这样碰到需要大数参与递推的题时你能自己设计数据结构。三层都过了高精度这块基本就稳了。3. 手写高精度模板从原理到代码3.1 数组模拟的核心思想模拟手算如果不用BigInteger最经典的高精度做法是用数组或字符串来模拟手算。这个思路说起来很简单我们小时候列竖式算加法就是一位一位对齐相加逢十进一。代码也是这么做。常见的存储方式有两种一种是从低位到高位存数组另一种是直接从字符串高位开始处理。我更推荐第一种因为处理进位和借位时下标从0开始非常方便。比如数字12345用int[] a存储时倒过来存就是a[0] 5; // 个位 a[1] 4; // 十位 a[2] 3; a[3] 2; a[4] 1; // 万位为什么要倒着存因为加法要做进位如果正着存个位下标是len - 1进位时下标变小处理起来绕来绕去。倒着存之后每一位的进位都往i 1方向推思路清晰很多。3.2 高精度加法模板与细节加法模板大概是这样的public static String add(String s1, String s2) { int[] a new int[s1.length()]; int[] b new int[s2.length()]; for (int i 0; i s1.length(); i) { a[i] s1.charAt(s1.length() - 1 - i) - 0; } for (int i 0; i s2.length(); i) { b[i] s2.charAt(s2.length() - 1 - i) - 0; } int len Math.max(s1.length(), s2.length()) 1; int[] c new int[len]; for (int i 0; i len; i) { if (i a.length) c[i] a[i]; if (i b.length) c[i] b[i]; c[i 1] c[i] / 10; // 进位 c[i] % 10; } // 去掉前导零并转为字符串 StringBuilder sb new StringBuilder(); int idx len - 1; while (idx 0 c[idx] 0) idx--; for (int i idx; i 0; i--) { sb.append(c[i]); } return sb.toString(); }这个模板里的关键是c[i 1] c[i] / 10这行。它模拟的就是“逢十进一”。如果你在比赛里手写最容易写错的地方就是进位的处理顺序一定要先算进位再取模否则进位就丢了。还有一个小细节结果数组长度要设置成Math.max(len1, len2) 1多出的那一位是为了存最高位的进位。比如999 1 1000最高位需要多一位才能放下。3.3 高精度减法借位才是灵魂减法比加法麻烦一点因为要处理“谁大谁小”和“借位”。我通常先写一个比较函数判断两个数的大小保证用大的减小的最后根据符号决定是否输出负号。public static String subtract(String s1, String s2) { boolean negative false; // 如果s1 s2则结果加负号并交换两个数 if (s1.length() s2.length() || (s1.length() s2.length() s1.compareTo(s2) 0)) { String tmp s1; s1 s2; s2 tmp; negative true; } int[] a new int[s1.length()]; int[] b new int[s2.length()]; for (int i 0; i s1.length(); i) { a[i] s1.charAt(s1.length() - 1 - i) - 0; } for (int i 0; i s2.length(); i) { b[i] s2.charAt(s2.length() - 1 - i) - 0; } int[] c new int[s1.length()]; for (int i 0; i s1.length(); i) { c[i] a[i]; if (i b.length) c[i] - b[i]; if (c[i] 0) { c[i] 10; int j i 1; // 借位从下一位借1如果下一位是0继续往后借 while (j s1.length() c[j] 0) { c[j] 9; j; } c[j]--; } } StringBuilder sb new StringBuilder(); int idx s1.length() - 1; while (idx 0 c[idx] 0) idx--; for (int i idx; i 0; i--) { sb.append(c[i]); } if (negative) { sb.insert(0, -); } return sb.toString(); }减法模板的借位逻辑很容易写乱特别是1024 - 999这种情况中间会连续借位。上面的写法是“向后找第一个非零位借1之后中间经过的0全部变成9”这个思路完全模拟了手算习惯之后就不容易错。不过说句实在话在正式比赛里我几乎不会手写减法模板因为有BigInteger.subtract。我写这个模板的主要目的是确保自己“真的懂”借位过程防止哪天题目环境特殊比如某些在线评测系统不让用BigInteger时手足无措。3.4 高精度乘法错位相加不迷路乘法比加减法更考验编码功底。核心思路是a的第i位和b的第j位相乘结果加到c[i j]上。这个i j就是所谓的“错位”。public static String multiply(String s1, String s2) { int n s1.length(), m s2.length(); int[] a new int[n]; int[] b new int[m]; for (int i 0; i n; i) a[i] s1.charAt(n - 1 - i) - 0; for (int i 0; i m; i) b[i] s2.charAt(m - 1 - i) - 0; int[] c new int[n m]; for (int i 0; i n; i) { for (int j 0; j m; j) { c[i j] a[i] * b[j]; } } // 统一处理进位 for (int i 0; i n m - 1; i) { c[i 1] c[i] / 10; c[i] % 10; } StringBuilder sb new StringBuilder(); int idx n m - 1; while (idx 0 c[idx] 0) idx--; for (int i idx; i 0; i--) { sb.append(c[i]); } return sb.toString(); }这个模板的精妙之处在于它没有在双重循环内部处理进位而是先让c[i j]累加所有乘积最后再统一进位。这样做的好处是逻辑简单不容易出错。代价是c[i]可能暂时超过10但int完全扛得住。注意一个细节两个长度分别为n和m的数相乘结果位数最多是n m所以数组开n m是足够的。4. 蓝桥杯高频题型与真题拆解4.1 典型真题大数加法变形题蓝桥杯的纯高精度题不会太难但会“包装”。比如给你一个很大的数字符串形式要求你求它加1之后的结果或者判断它是不是回文数。这里有一个关键点输入可能是几百位的字符串直接转long会溢出必须按字符串或BigInteger处理。我之前看到一个很典型的例子“1-9 高精度减法(subtraction) 分数10 作者 jackson 单位 上海大学”这是很多学校Java课程的经典大作业题要求计算两个大整数之差。题目描述非常简单但恰恰能考出你对字符串处理、借位逻辑、负数判断的掌握程度。这种题我建议你先用BigInteger写一版快速通过的代码再用手写模板实现一遍对比两种写法的代码量和出错率感受一下差距。我自己这么练过之后最大的收获是明白了“库函数节省的不仅是时间还有心智负担”。但也知道了“在某些特殊场景下手写模板能帮我把数据结构和算法思想打通”。4.2 高精度递推斐波那契与卡特兰数蓝桥杯考高精度经常是把它嵌在递推题里。比如求斐波那契数列的第n项n到了1000以上结果已经远超long范围这时候你就必须在递推里用大数。如果使用BigInteger代码很直接BigInteger[] fib new BigInteger[n 1]; fib[0] BigInteger.ZERO; fib[1] BigInteger.ONE; for (int i 2; i n; i) { fib[i] fib[i - 1].add(fib[i - 2]); }这种题对于会BigInteger的人来说就是送分题。但问题是有些递归写法会超时因为你重复计算了大量子问题。此时就算你用了BigInteger也没用因为性能瓶颈在算法层面。所以遇到这种题正确的解题姿势是先优化算法比如记忆化、滚动变量再套用大数类型。卡特兰数也是一样的道理。递推式C(n1) C(n) * (4n 2) / (n 2)里既有乘法又有除法用BigInteger做除法时要特别小心因为BigInteger的整数除法会截断小数。好在卡特兰数本身一定是整数用divide不会出问题前提是你算的过程中不要有精度丢失。4.3 大数阶乘的两种写法对比求n!是蓝桥杯里非常经典的高精度题目n到1000时结果已经是天文数字。用BigInteger写代码非常优雅BigInteger res BigInteger.ONE; for (int i 2; i n; i) { res res.multiply(BigInteger.valueOf(i)); }这段代码的时间复杂度是O(n * 大数乘法复杂度)在n 1000的时候一点问题都没有。但如果你想追求极致的效率可以改成“分段乘”或者用数组手写累乘不过这属于竞赛优化范畴备赛初期不需要太纠结。我在备赛时专门对比过同一个n500的阶乘BigInteger版本写起来不到一分钟手写数组模拟要用Classic模板反复调代码量翻倍运行时间反而没有显著优势。因此在蓝桥杯这种“求稳大于炫技”的比赛中我强烈建议你用BigInteger。5. 备赛调试避坑清单5.1 前导零与字符串输出无论你是用BigInteger还是手写模板输出的时候都要注意前导零。BigInteger的toString已经帮你处理好了但手写模板需要自己处理。我在模板里写的while (idx 0 c[idx] 0) idx--;就是为了跳过高位多余的0。如果不处理123 0可能会输出0123直接WA。5.2 负数与符号处理大数减法里最容易翻车的是负数。如果你用BigInteger直接subtract就完事了符号自动处理。如果你手写一定要先比较大小。我自己的习惯是只要题目没有特别限制优先用BigInteger因为它对符号、零、负数的处理非常完善我不用在细节上反复测试。5.3 性能瓶颈与超时排查用BigInteger超时的情况我遇到过两次一次是循环次数太多一次是没做预处理。排查思路很简单先看算法是不是有重复计算比如递归里反复new BigInteger。再看不必要的大数运算能不能用long替代比如某些中间量虽然最终结果很大但中间过程很小可以先算long再转BigInteger。最后看能不能用快速幂替代普通循环里的连乘。5.4 输入输出的配合技巧蓝桥杯的在线评测系统对输入输出的稳定性要求很高。大数输入通常是用String接收然后转成BigInteger输出直接System.out.println。如果你的程序要输出几千位的数println完全没问题不要手动拼字符串再输出那样反而容易错。另外如果你用BigDecimal处理浮点大数输出时注意去掉末尾多余的0可以用stripTrailingZeros()方法。蓝桥杯有时候会要求“输出整数部分”你直接.toBigInteger()转换就行。聊到这儿高精度这块就算梳理得差不多了。我个人在实际备赛中的体会是高精度题从来不是蓝桥杯的难点核心但它是那种“会了就稳拿不会就干瞪眼”的知识点。你不需要把每个手写模板都背得滚瓜烂熟但一定要知道原理知道什么时候用BigInteger什么时候必须自己模拟。最后再分享一个小技巧刷高精度题的时候建议你每次都用两种方式各写一遍——先BigInteger快速AC再手写模拟一遍。这样既能保证比赛时的正确率又能让你真正理解大数运算的本质。等你练熟了看到“1000位整数求和”这类题第一反应就不会是“这怎么算”而是“一行add搞定”。这种游刃有余的状态就是Day10最大的收获。
