这道题在PTA天梯赛题单里一直被我当成“检验基本功”的经典题。L1-111大幂数光看名字就知道要处理一个非常大的幂结果很多同学一上来就用循环累乘结果要么超时要么发现long long根本存不下。这篇题解我会把题目拆成“高精度乘法”和“快速幂”两个点从思路到代码再到实际调试和边界测试完整走一遍希望能帮正在刷天梯赛题单的同学把这题吃透顺便把大数运算的底子打牢。1. 这道题到底考什么把大幂数拆成两件事1.1 大幂数的常见题目设定大幂数这类题目的基本设定一般很简单输入一个底数a和一个指数b要求输出a^b的完整十进制结果。听起来是不是比天梯赛L2那些带图论、带动态规划的题“亲民”多了但实际一写就会发现它卡在两个很实在的地方结果可能非常长普通整型变量根本放不下。指数b如果比较大直接连乘会做很多次大整数运算时间上扛不住。所以这题真正想考察的并不是你会不会调pow函数而是你能不能把“大数存储”和“快速幂”这两个基本功组合起来用。天梯赛L1阶段的题通常不会故意给一个结果长达几十万位的极端数据但数据范围设计得刚好让“暴力循环乘”吃力或者说让标准写法在更广的范围内都能稳定通过。1.2 为什么暴力循环累乘一定有问题先聊一个最直接的思路for循环乘以b次。假设a小于10b等于1000那么2^1000大约有302位十进制已经远超unsigned long long的表示范围。一旦中间结果超范围后续乘法全错。有人可能会说那就用字符串手动乘啊。可以但又不完全对。假设b是10万你每循环一次都要做一次大数乘法每次乘法要遍历当前数字的所有位时间复杂度大致是O(b × 位数)指数稍微大一点就直接超时。在竞赛环境里很可能一个大样例就把这个方案送走了。我觉得这类题最好的处理思路就是把“快速幂”当作外层框架把“高精度乘法”当作内层基础操作。快速幂负责把指数b的运算次数从O(b)降到O(log b)高精度乘法负责解决结果位数过长的问题。二者配合起来才是这题比较完整的解法。1.3 两个核心考点是怎么结合起来的如果把整个算法想象成一台机器快速幂是“控制中枢”高精度乘法是“执行机构”。快速幂会告诉你当前二进制位是不是1决定要不要把现在的base乘进结果。高精度乘法会告诉你两个上百位的数字相乘每一位怎么算进位往哪里放。理解了这层关系写代码时就不会把两部分混在一起。很多人写大数快速幂容易乱就是因为脑子里只记得快速幂的框架却在“乘法”环节用了普通整型或者在乘法时忘了处理进位。先分清职责后面每一步都会清晰很多。2. 方案选型数组模拟、字符串模拟还是压位2.1 字符串模拟和高精度数组有什么区别大数的常用表示方法有两种一种是直接用字符串存储一种是用int数组存储。字符串模拟最容易理解每一位字符就是一个数字字符乘法时模拟竖式计算。好处是打印输出方便从字符串直接倒序输出就行坏处是字符串会频繁创建临时对象在快速幂循环中进行大数乘法时如果不够细心性能会打折扣。数组模拟的核心思路其实和竖式乘法一模一样但每个元素是一个真正的int数字处理进位时直接用数字运算。数组的好处是下标操作直观乘法过程中可以用res[i j] x[i] * y[j]一次性完成累加然后再统一进位代码效率高不少。考虑到天梯赛题目一般数据范围设计得不会过于极端十进制数组已经足够用了。但如果数值位数特别大比如几千位几万位还可以用“万进制”压位也就是每个数组元素存储0到9999之间的数而不是0到9。这样数组长度直接缩短到原来的四分之一内层乘法循环次数也会大幅减少。2.2 十进制存储和万进制存储怎么选先上一张对比表方便你直观感受存储方式每位表示范围数组长度进位处理输出方式适用场景十进制数组0~9较长向下一位进1处理简单逆序输出每一位代码直观适合新手万进制数组0~9999较短向下一位进10000进位更少逆序输出时不足四位要补0位数很大时性能更好十进制数组在乘法过程中的中间值res[i j] x[i] * y[j]最大值可能达到几万甚至几十万所以要记得在统一进位时处理整除和取余这个逻辑对所有进制都通用。万进制只是把“满10进一”改成“满10000进一”核心思想完全一样但位数的减少会让乘法、进位、去前导零这些操作的耗时明显下降。一般在写题解或者调试时我建议先用十进制数组跑通整个逻辑再用压位优化性能。不要一上来就写万进制否则进位和补0输出两个地方同时出错时很难排查。2.3 为什么最终选择“数组 快速幂”我自己做这类题时默认采用“int数组存储 十进制进位 快速幂”的方案原因很实在数组下标从低位开始存乘法和进位的逻辑直接对应数学竖式不容易写错。快速幂里需要反复调用乘法函数用vectorint对象直接返回代码简化很多。十进制输出最方便不用额外补零对新手来说调试成本最低。等这个版本完全跑通再考虑压位也不迟。竞赛或在PTA提交时往往最怕的不是常数慢一点而是逻辑错误。先保证逻辑正确再去抠性能。3. 核心实现高精度乘法和快速幂的代码级拆解3.1 高精度乘法的底层逻辑高精度乘法的核心就一句话用数组下标模拟每个数字的“10的幂次”。举个例子数字x的第i位表示x[i] × 10^i数字y的第j位表示y[j] × 10^j两者相乘后得到的是x[i] × y[j] × 10^(ij)所以应该累加到结果的第ij位。这就是res[i j] x[i] * y[j]这行代码的由来。累加完成后每一位可能超过9所以要统一进位。进位从低位到高位处理把当前位的值除以10商加到下一位余数留在本位。如果最高位还有进位就在数组末尾继续追加元素。最后再把最高位多余的0去掉也就是“去前导零”。比如999 × 11最高位运算后可能多出一个0不弹掉的话输出结果前面就会多一个0。vectorint multiply(const vectorint x, const vectorint y) { vectorint z(x.size() y.size() 1, 0); for (int i 0; i (int)x.size(); i) { for (int j 0; j (int)y.size(); j) { z[i j] x[i] * y[j]; } } int carry 0; for (int i 0; i (int)z.size(); i) { int cur z[i] carry; z[i] cur % 10; carry cur / 10; } while (carry) { z.push_back(carry % 10); carry / 10; } while (z.size() 1 z.back() 0) { z.pop_back(); } return z; }这里面有个细节z的初始长度设为x.size() y.size() 1已经预留了最高位进位的空间。但为了保险进位处理完后仍然用while (carry)把可能超过初始长度的进位追加到末尾。去前导零的while条件里写z.size() 1很重要。如果结果是0我们希望结果还是保留一位0而不是一个空数组。3.2 快速幂框架和控制流程快速幂的核心思想是把指数b拆成二进制。比如b等于13二进制是1101也就是13 8 4 1。那么a^13就可以写成a^8 × a^4 × a^1。实现时我不断把底数base平方同时把指数b右移。如果当前b的最低位是1就把base乘进结果res。这样循环下去只需要大约log2(b)次迭代而不是b次。结合大数乘法时具体框架如下res初始化为{1}对应a^0。base初始化为底数a的十进制数组比如a2时base存储为{2}。每次循环判断b的最低位如果为1则res multiply(res, base)。然后b右移一位同时base multiply(base, base)。这里有个容易踩坑的点如果写成while (b) { if (b 1) res multiply(res, base); base multiply(base, base); b 1; }最后那次base平方其实已经用不上了白白做了一次大数乘法。当然数据量不大时这个问题不大但为了性能更优我习惯在b右移后再判断if (b 0)才平方while (b 0) { if (b 1LL) { res multiply(res, base); } b 1; if (b 0) { base multiply(base, base); } }这样最后一次迭代结束后不会多算一次无意义的平方。3.3 完整可运行的C代码把乘法函数和快速幂函数拼在一起就是一个可以直接提交的完整版本#include bits/stdc.h using namespace std; vectorint multiply(const vectorint x, const vectorint y) { vectorint z(x.size() y.size() 1, 0); for (int i 0; i (int)x.size(); i) { for (int j 0; j (int)y.size(); j) { z[i j] x[i] * y[j]; } } int carry 0; for (int i 0; i (int)z.size(); i) { int cur z[i] carry; z[i] cur % 10; carry cur / 10; } while (carry) { z.push_back(carry % 10); carry / 10; } while (z.size() 1 z.back() 0) { z.pop_back(); } return z; } vectorint quickPower(int a, long long b) { vectorint base; while (a 0) { base.push_back(a % 10); a / 10; } if (base.empty()) { base.push_back(0); } vectorint res {1}; while (b 0) { if (b 1LL) { res multiply(res, base); } b 1; if (b 0) { base multiply(base, base); } } return res; } int main() { int a; long long b; while (cin a b) { vectorint ans quickPower(a, b); for (int i (int)ans.size() - 1; i 0; --i) { cout ans[i]; } cout \n; } return 0; }这里要注意几点数组存储是低位在前比如数字8192存储为{2, 9, 1, 8}。输出时必须倒序打印。quickPower函数里我把传入的a直接改掉了因为后面已经不需要原值。如果底数为0base会变成{0}如果指数b为0res保持{1}最后输出1。这是目前比较通用的约定如果你的题明确不出现0^0这种用例那这段代码完全没问题。3.4 如果题目要求的是“取模”不是输出完整结果大幂数还有一种常见变形是输出a^b对某个数取模的结果。比如指数b可能高达10^18但只需要输出模M后的余数这种题就不需要手写高精度乘法。如果是取模版本快速幂的乘法直接用long long配合模运算就能做核心代码如下long long quickPowMod(long long a, long long b, long long mod) { long long res 1; a % mod; while (b 0) { if (b 1LL) { res res * a % mod; } a a * a % mod; b 1; } return res; }所以看到题目时要先判断清楚是要“完整大数输出”还是“取模余数”。前者用高精度后者用普通快速幂方向千万别搞混。4. 实操演示用手算把完整过程走一遍4.1 用2的13次方验证快速幂流程纸上谈兵不如实际演算一遍。以底数2、指数13为例13的二进制是1101快速幂过程如下步骤b的当前值b二进制是否乘baseres变化base变化初始131101-12第1轮131101是1×22base平方为4第2轮6110否不变base平方为16第3轮311是2×1632base平方为256第4轮11是32×2568192结束最终结果8192完全正确。这个演算过程其实和普通快速幂完全一致唯一的区别是这里每次乘的都是大数字底层调用的是高精度乘法函数。4.2 一批必测的边界用例做这种题建议提交前先跑以下这组用例输入期望输出说明2 138192常规用例2 01任何非零数的0次方为13 13指数为11 100001底数为1结果永远10 50底数为0且指数大于09 3042391158275216203514294433201验证大数乘法进位和多位输出其中9的30次方那组测试很多人在调试时容易算错或看花眼建议对照一个在线计算器或者Python的9 ** 30去验证一下输出。4.3 调试时最高效的三个技巧第一对拍验证。写一个最简单的暴力循环版本只支持int范围内的小指数然后用随机小数据不断和自己的高精度快速幂对比结果。这一步能筛掉绝大部分逻辑错误。第二打印中间变量。在quickPower里临时加上printf每次循环输出b、res和base的十进制值一眼就能看出来是res少乘了一次还是base平方时机不对。第三检查存储方向。很多人调试时会把数组从头到尾输出结果看到的是倒序数字就会误以为结果错了。记住预处理和打印是两套逻辑存储低位在前打印一定要从数组末尾往开头走。5. 常见问题与排查技巧实录5.1 为什么结果末尾少了一位或多了几个0这种情况多半是进位处理有问题。如果只处理了乘法的内部进位但忘了处理最高位之后的进位就会少位。比如99×99乘积是9801按乘法累加后第2位可能已经超过10如果没把进位加到第3位就变成801最后一位就丢了。另一个常见原因是去前导零的时机不对。快速幂循环过程中如果multiply返回了一个带有前导零的结果后面继续参与乘法时并不会影响正确性但最终输出时就会多出0。建议在每次乘法返回时都统一去掉前导零保证数组长度最小化。5.2 快速幂结果为什么总是差一个因子比较典型的原因是res初始值写错。res应该初始化为1代表0次幂的结果。如果把res初始化为0不管乘多少次结果都是0。另一个原因是base平方的时机不对。如果在判断b 1之前就提前平方了一次相当于指数翻倍结果自然对不上。建议把快速幂的循环逻辑固定成一句话“先判断当前最低位再右移指数最后平方底数”。只要顺序不乱这类问题基本能避免。5.3 乘法函数调用很多次运行很慢怎么办高精度乘法的复杂度是O(len1 × len2)快速幂会调用大约2log2(b)次乘法函数。如果数据位数比较长性能确实可能吃紧。优化方向从大到小排把十进制数组改成万进制数组位数变成原来的四分之一乘法次数指数级减少。减少vector的拷贝次数。比如在multiply中可以使用vectorint引用传入返回时也可以考虑用函数内static变量不过会牺牲一些代码简洁性。循环边界写紧一点。比如x.size()和y.size()在循环外先取出来避免每次循环都调用size()方法。天梯赛L1的数据范围一般不会逼你用特别极端的优化但如果想把这个能力迁移到以后的算法题里压位优化是很值得掌握的一招。5.4 在PTA提交时需要注意什么PTA对代码格式要求比较严格但L1题目一般允许使用bits/stdc.h万能头文件方便很多。提交时注意几点函数返回vector 时编译器版本要支持C11以上。指数b如果题目说可能很大记得用long long读入不要用int。输出结果之后记得换行PTA很多题目对行尾是否有换行没有强制要求但保持输出整洁是习惯。如果本地运行正常但提交后报“段错误”优先检查是不是数组越界。尤其是z[i j] x[i] * y[j]时如果z的空间没有预留足够大就可能越界。我的代码里初始长度是x.size() y.size() 1正常场景下都够用但如果你自己改动过乘法逻辑一定要重新检查下标范围。6. 这道题还能延伸到哪些方向6.1 从大数幂到大数阶乘大数幂和高精度乘法掌握了顺手就能写大数阶乘。比如计算1000!思路是用一个数组存结果然后从2乘到1000每次调用一次高精度乘法。这个方向在很多算法题里会用到比如组合数、概率统计中的精确计算等。6.2 从普通快速幂到矩阵快速幂普通快速幂把底数看成整数矩阵快速幂把底数看成一个矩阵框架几乎一样只是把乘法换成矩阵乘法。斐波那契数列的O(log n)解法本质上就是矩阵快速幂。理解了今天这个题以后学矩阵快速幂会轻松很多。6.3 从完整输出到余数题如果题目只需要输出对10^97取模的结果直接用long long快速幂代码短得多。LeetCode上有一道很经典的“超级次方”恰好就是把指数用数组形式给出再配合取模快速幂处理。你会发现这些题的核心都是同一个框架拆指数二进制、平方累乘、判断位数。我自己第一次认真写这道题时也栽过跟头。当时把res初始成了0死活跑不出正确结果后来一步步打印中间变量才发现是对概念理解不透。所以还是那句话做这种“模板题”千万不要只背代码一定要亲手跑一遍过程把边界试个遍。这篇题解里的可执行代码和测试用例建议你直接复制到本地环境里跑一跑再按自己的理解重新写一遍比单纯看十遍都管用。