天梯赛L1-111大幂数题解：C语言高精度幂运算全解析

天梯赛L1刷到后半段题目就开始搞事情了。前面几题还在考printf保留两位小数这种基本功突然冒出一道“大幂数”让不少人原地卡住。我第一次看到这题的时候心里想的是幂运算直接调用pow不就行了结果随手试了个样例输出长得吓人——这压根不是一个int、long long能装下的整数。这道L1-111大幂数题解说的就是高精度整数幂题目让你算一个很大的幂常见版本是输入N输出2^N的完整十进制结果而N大到结果位数轻松超过普通内置整数类型的上限。以2^1000为例输出有302位而long long最多撑到2^63。所以这道题真正考的不是数学而是大数运算的基本功用数组模拟竖式乘法一位一位地把结果存下来。这篇文章我会从题目拆解、核心原理、C语言完整实现、踩坑记录一直聊到进阶的大数运算方向。无论是正在备战天梯赛、刚学C语言没多久还是已经见过这道题但没完全搞懂高精度流程的同学都可以按这个思路从头走一遍。全文会用最直白的方式讲清楚每一个细节包括进位怎么处理、数组为什么倒着存、n0这种边界怎么应付保证你合上文章就能自己默写出代码。1. 先看懂题目大幂数到底考什么1.1 题目说的“大”有多大先说结论这张卷子的L1题绝大多数都不需要你发明算法但要你对“数据范围”有概念。大幂数这道题数据范围就很典型。如果题目要求计算2^NN给到几千甚至上万结果会是多少位我直接算给你看一个数M的十进制位数等于floor(log10(M)) 1所以2^N的位数大约是N乘以0.3010再加1。N10000的时候结果有3011位。有几位是多大概念一个int才10位封顶一个long long最多19位unsigned long long极限也就20位。3011位这个数字你就算把电脑里的所有整数类型全拼一起也不够装。所以题目里的“大”不是一个形容词而是一个强制要求你必须自己设计一种能表示超长整数的方式。常见的做法是用数组数组下标对应每一位数字。这是高精度计算最基本的思想也是这道题真正的考察点。如果题目输入是两个数a和n要你算a^n原理一模一样就是把固定乘2改成固定乘a而已。我后面给通用版本代码可以直接套用。1.2 三个隐藏考点我刷了这么多年题发现这类题表面是“计算”实际上在考三件事。第一大数存储方式你要知道普通变量装不下得用数组逐位存数字并且要决定低位放在数组前面还是后面。第二竖式乘法模拟手算乘法怎么算程序就怎么写核心是“逐位相乘”和“逢十进一”的进位处理。第三边界和输出格式题目不会明说“你要处理n0”但测试数据一定会给这种边界输出时如果从数组错误的方向打印结果就是反向数字。这三件事听起来都不难但组合在一起就是一道很典型的“L1后段”题目。天梯赛的套路就是这样算法不难细节要命。你会发现在考场上一堆人不是因为不会算2^n挂掉的而是因为数组开小了、进位的位置写错、输出顺序搞反这种白给分丢得非常可惜。1.3 为什么不能直接用int或double可能有同学会问我用double存不行吗double的精度撑死也就15到16位有效数字。2^100有31位double存下来是1.2676506002282294e30后面一堆位全靠舍入早就不是精确值了。你要输出完整结果double直接判死刑。那Python呢Python的int确实没有上限刷题确实方便。但天梯赛的主力语言是C/C而且高精度本身是程序设计的基本功靠解释器自带功能绕过去等于没练习到核心内容。就算让用Python当结果有几千几万位时字符串拼接和转int的耗时也会让你吃亏。所以老老实实用C数组模拟竖式才是正道。2. 核心原理高精度幂运算手算一遍你就懂2.1 数组存数低位在前是这套模板的灵魂用数组存一个多位数之前必须先做一个决定把个位放在数组下标0的位置还是把最高位放在下标0。我强烈推荐低位在前也就是ans[0]存个位、ans[1]存十位、ans[2]存百位依此类推。举个例子数字12345在低位在前的数组里就存成ans[0]5, ans[1]4, ans[2]3, ans[3]2, ans[4]1。需要输出的时候倒着打印就行。为什么要这样因为进位总是从低位往高位走的。乘法过程中如果产生新的数位那一定是往最高位的方向扩展也就是数组尾部追加。数组尾部追加很容易直接ans[len] 新位就行。反过来如果你把最高位放在下标0一旦产生新最高位就需要把所有原有数字往数组尾部移动腾出头部位置这个操作效率低不说还特别容易写错。我见过很多同学在这个选择上栽跟头最后输出乱成一团。低位在前是这类模板的“灵魂”先接受它后面所有代码都会顺很多。2.2 一次乘法的完整手算过程光说理论不好理解我拿一次实际乘法来演示。假设现在是2^3结果是8数组里存着ans[0]8len1。现在要变成2^4就是整个数组每一位都乘以2再处理进位。第一步处理第0位8乘以2等于16。当前位只能留一个数字所以ans[0]变成6多出来的1作为进位带入下一位。第二步原本数组的len只有1看起来没有下一位了但进位1不能丢。于是我们把1追加到数组尾部ans[1]1len变成2。此时数组内容从低位到高位是[6,1]倒过来就是16答案正确。整个过程和手算竖式一模一样只是把纸上的“进位”变成了程序里的carry变量。再看一个会发生连续进位的例子。2^416数组是[6,1]要乘2变2^5。第0位6乘2得12ans[0]写2carry1。第1位1乘2再加carry的1得3ans[1]写3carry0。循环结束没有额外进位数组变成[2,3]倒序输出就是32。两次演示看下来你应该已经明白每次循环就是把当前所有位乘以2然后用carry记录“多出来的十位以上部分”等下一位时一起算进去。2.3 位数估算提前判断数组要开多大写高精度最害怕的就是数组开小了结果数据一进位就越界。避免越界最靠谱的方法是在写代码前估算一下最大位数。对于2^N前面说过的公式是位数约等于N乘以0.3010再加1。因为log10(2)约等于0.3010。如果你不想记这么精确的小数就记一个比赛里非常实用的近似“2的10次方约等于1024近似10的3次方”。也就是说每乘10次大约多3位。N10000那就大约多3000位再加上头几位开3200的数组非常稳。我列了一张常见规模表方便你直接对照N2^N结果位数建议数组容量1003150100030235050001506160010000301132001000003010330200如果是a^n这类通用版本位数估算公式就变成n乘以log10(a)再加1。比如3^10000因为log10(3)约等于0.4771位数大概4771位。估算完之后数组容量在这个值基础上再加个二三十既是保险也不浪费内存。我自己的习惯是固定写成估算值加10一次到位从不返工。2.4 复杂度为什么暴力乘n次也能过有同学看到要循环乘N次每次还要遍历整段数字第一反应是这是不是太慢了。其实完全不用担心。设最终结果位数为LL约等于0.301N。每次乘法遍历当前位数而位数从1慢慢增长到L所以总操作次数大约是123...L也就是L(L1)/2约等于0.045N^2。N10000时这个量级是450万次左右加上进位等简单运算撑死几千万次操作C语言一秒内跑完绰绰有余。所以这道题用最朴素的外层循环乘N次完全没问题。真正的效率隐患只出现在N超过十万甚至百万的时候那时才需要引入快速幂思想我第5章会提。就L1的数据范围来说暴力就是最合适的方案不要给自己加戏。如果你提交超时了大概率不是乘法本身的问题而是别的操作出了问题后面排查章我会讲。3. 完整代码C语言实现与逐段讲解3.1 精简版固定算2的N次幂先给一个最精简的版本假设题目就是输入N输出2^N#include stdio.h int main() { int n; scanf(%d, n); int ans[5000] {0}; int len 1; ans[0] 1; for (int i 0; i n; i) { int carry 0; for (int j 0; j len; j) { int t ans[j] * 2 carry; ans[j] t % 10; carry t / 10; } while (carry) { ans[len] carry % 10; carry / 10; } } for (int i len - 1; i 0; i--) { printf(%d, ans[i]); } printf(\n); return 0; }这套代码的核心就是每次循环把当前整个数组乘以2。ans[0]1相当于是2^0循环执行n次后就是2^n。内部循环处理已有len位t表示当前位乘以2再加上低位的进位然后拆成当前位和新的进位。最关键的while(carry)确保了高位扩展不会丢数。你可以在草稿纸上用n5走一遍这段代码输出就是32。3.2 通用版算a的n次幂如果题目不是固定算2而是输入两个数a和n要输出a^n的精确值代码几乎不用改只要把固定乘2改成乘变量a#include stdio.h int main() { int a, n; scanf(%d %d, a, n); int ans[5000] {0}; int len 1; ans[0] 1; for (int i 0; i n; i) { int carry 0; for (int j 0; j len; j) { int t ans[j] * a carry; ans[j] t % 10; carry t / 10; } while (carry) { ans[len] carry % 10; carry / 10; } } for (int i len - 1; i 0; i--) { printf(%d, ans[i]); } printf(\n); return 0; }这里唯一需要注意的点是当a变大时一位数乘以a再加大进位的结果t可能变得比较大比如a99t最大可能到891但int完全存得下所以不用慌。如果题目不保证a小于10carry用int依然足够。还有一点如果输入a0且n0第一次乘完后ans[0]0之后保持0输出0逻辑正确如果n0循环不执行输出1通常题目也就是这个约定。通用版本在字节跳动和LeetCode风格的题里也经常能用上建议理解后固化成自己的模板。3.3 Python对照拿来验证再合适不过用C写高精度最怕的就是自己心里没底错了也找不到问题。我的习惯是用Python写一份完全对应的逻辑来验证。Python自带大整数你可以直接用内置函数看标准答案也可以手写同样的数组模拟确认逻辑完全一致def power_int(a, n): ans [1] for _ in range(n): carry 0 for i in range(len(ans)): t ans[i] * a carry ans[i] t % 10 carry t // 10 while carry: ans.append(carry % 10) carry // 10 return .join(map(str, reversed(ans))) print(power_int(2, 100))这段Python和C逻辑一一对应跑出来的结果可以直接当标准答案。当然你也能直接print(pow(2, 100))拿到系统级大整数结果来核对。我通常的验证路线是先用Python内置大数算几个关键点再用Python模拟高精度算一遍确认逻辑一致后才放心去调C代码。这套工作流看起来多了一步实际能省下大量调试时间。3.4 自测数据背下这7组输出写完全代码之后不能光靠题目给的样例就提交。我建议你把这些数据挨个测一遍确认输出完全一致输入输出011253210102416655362010485761001267650600228229401496703205376这七组覆盖了0次幂、小规模、产生连续进位、位数扩展、大数字等情况。前几组能查出输出顺序和进位逻辑的问题最后一组能测试数组容量和长数位稳定性。如果这七组全都对得上你的程序大概率就稳了。需要注意的是最后一组只有31位如果你想更严格测数组容量可以直接输入10000然后拿在线工具核对2^10000的结果不过只要位数估算做得对这个测试通常不会出问题。4. 常见问题与排查技巧实录4.1 输出完全反过来问题出在哪这是高精度新手最常见的问题。比如输入5程序输出了23而正确结果是32。你一看就明白了数字的每一位都倒过来了。原因只有一个——输出方向反了。因为数组低位在前面个位在ans[0]输出时必须从len-1倒着打印到0。如果你从0开始正着打印输出的就是个位、十位、百位这样的逆序。这个错误非常好发现看到输出和自己手算的结果数字顺序相反基本就是它。解决办法是输出循环改成for (int i len - 1; i 0; i--)。还有一个变体问题有人把数组清零范围搞错导致输出时前面多了一串0那也是在看位长时没弄对len而不是乘法错。4.2 最高位神秘消失另一个高频错误是输入4输出却是6。为什么会这样因为你只写了ans[j]的更新忘了处理新产生的进位位。比如8乘2得16你把个位6写进了ans[0]然后就觉得完事了carry里的1没人管于是最高位丢了。正确做法是内层循环结束后必须用while(carry)把进位一位一位追加到数组尾部。有的同学会写成“if (carry) ans[len] carry;”这在乘2时没问题因为carry只可能是1。但如果你在通用版里算a^ncarry可能超过9比如99乘9得891进位是89你用一个int直接存还行但位数增多时必须把89拆成8和9两个数位。所以统一写成while(carry)最稳妥不管carry是几都能正确扩展位数。4.3 数组越界本地正常一提交就段错误我在新手期栽过最狠的坑就是数组开小。有一次我图省事int ans[100]开得特别小跑小数据完全正常一输入大N程序要么输出一堆乱码要么直接崩溃。更折磨的是有时候本地编译器没报错提交到OJ上却是段错误或答案错误。原因就是高位进位把数据写到了数组边界之外破坏相邻内存。解决思路其实很朴素写代码前用第2.3节的估算公式算一下最大位数再开数组。比如N是10000那就开4000保险一点开5000。如果题目没有说明N范围你宁可开一个接近内存上限的大数组也不要卡着边界。我习惯是在估算值上再加10到20个空位既能防止极端情况也不会浪费多少空间。4.4 时间超限的误判有的同学在高精度乘法里加了很多不必要的操作结果提交超时第一反应是“哎我不该用暴力乘n次”。其实L1的数据范围下暴力乘法完全够用超时往往是别的原因。一个典型的坑是输出环节如果你用printf(%d, ans[i])循环输出几千位这个没问题但如果你在每次循环里额外做字符串拼接、反复分配内存那就会非常慢。另一个可能是在循环内部又做了一次数组清零把整个长度为5000的数组重新赋0白白增加几千万次操作。还有如果你的数组开成MAXN但内循环却总是遍历整个MAXN而不是遍历当前len也会把复杂度提升一个量级。排查超时先看内层循环是否用了len而不是固定大数组长度再看有没有多余的数组初始化最后看输出是否用了一次性拼接或大量缓存拼接。这三步排查完绝大多数超时都不是算法本身的问题。4.5 提交前自查清单我在考场上的习惯是提交前花十秒钟过一遍这个清单数组容量够不够ans[0]有没有初始化为1len有没有正确表示当前位数内层循环是不是只遍历到len进位有没有用while(carry)处理完输出是不是从len-1倒序到0最后有没有输出换行这一套检查下来我已经数不清帮我拦住了多少次白给的提交。尤其是换行那一条很多题目的格式要求输出后跟一个换行你忘了也不会有编译错误但就是Wrong Answer非常冤。5. 延伸从大幂数到大数全家桶与快速幂5.1 高精度四则运算的通用套路大幂数这道题练熟之后你就已经掌握了大数运算里最核心的“高精度乘单精度”部分。所谓单精度就是大数乘以一个int范围的小数字。高精度加法也一样同步遍历两个数组逐位相加carry记录进位高精度减法则需要先比较大小再按位相减借位机制是模拟退位。真正复杂一点的是高精度乘以高精度也就是大数乘以大数那需要双重循环用结果数组的第ij位累加乘积最后统一处理进位。这四类运算都是天梯赛L2、蓝桥杯这类比赛里的高频考点。我的建议是把大数四则运算集中写一次存成自己的模板代码考前一小时默写几遍形成肌肉记忆。5.2 当指数大到不能硬乘如果题目不要求输出完整大数而是要求a^n对某个数取模那“暴力乘n次”就不再适用得换快速幂。快速幂的核心思想是“指数二分”把n拆成二进制例如2^13拆成2^8、2^4、2^1的乘积这样只需要乘log2(n)次。算法里保留一个中间变量每次把底数平方如果当前二进制位是1就把底数乘进答案。经典的取模快速幂代码很短long long pow_mod(long long a, long long b, long long mod) { long long res 1 % mod; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }如果既要精确大数结果、指数又大得离谱那就要把“快速幂”和“高精度×高精度”组合起来用二进制展开指数维护两个大数变量一个存当前底数的幂一个存把对应二进制位乘入后的结果。这个思路在天梯赛L2的一些题里出现过但L1-111本身用不上你可以先了解等刷L2时再深入。5.3 天梯赛备考顺序建议结合天梯赛的题目分布我建议你把高精度相关的学习顺序排成先练大数加法再练高精度乘单精度也就是这道大幂数然后练高精度乘高精度最后练取模快速幂。这个顺序由易到难而且每一步的代码量都在增加但对内存、进位、边界的要求是一脉相承的。如果你已经刷到了L1-111这道题说明前面的字符串、结构体、排序问题处理得差不多了接下来可以进入L2模拟题和更高阶数据结构的练习。只用一道题打天下是不可能的但大数基本功过关确实能让你在后面省下不少力气。6. 最后说点考场上的经验这套高精度模板我前前后后改了不知道多少遍。第一次独立写大幂数时我数组只开了1000结果N一上3000就崩后来学了位数估算才知道log10(2)这个常数有多好用。还有一次是输出时忘了倒序对着“23”和“32”发了五分钟呆才发现是这种低级错误。从那以后我养成一个习惯任何高精度题写代码前先估算最大位数为了让每一个判断都落在实处。也希望你在刷题的时候别只背代码而是能说出每一步在模拟手算的哪一步这样遇到题目的任何变体都能稳得住。如果这篇文章对你有帮助可以照着代码跑一遍把第3.4节的测试数据都验一遍有问题随手在草稿纸上推一遍比我单独给你讲十遍都管用。