计算2的n次方（大整数乘法）

题目

计算2的n次方，n<=10000。

思路

由于计算的结果可能非常大，甚至 long long 都存不下，所以我们考虑用数组存储结果的每一位，前面的存低位，后面存高位，比如说a[0]存的是个位，然后a[1]存十位等。

我们用 size 记录当前计算的结果的位数，并初始化为1。将 a[0] 设置为1，一方面是 2^0=1，另一方面是我们算乘法，一个数 * 1 = 本身，适合乘法的初始化，同理加法的初始化我们应该初始化为0。

基本工作做好了以后，就是接下来是关键步骤了。

计算n次乘法，每次都对数组进行更新。首先定义一个进位 t，并初始化为 0，然后进行一次乘法，这里其实模拟的是笔算乘法，我们用 t 暂时存放更新前当前位*2+进位 t 的结果，然后更新后当前位= t % 10，就是取最低位，然后进位 t 更新为 t / 10，由于是十进制，所以除以10，然后整数除法，若为达到10，则 / 10 的结果是 0，否则就是进位，都符合进位的定义。然后如果处理后还有进位，那么说明 size 得扩大一位了，而且该位的结果就是进位 t 。

最后就是输出结果了，记得我们存的是由低位到高位，所以我们需要逆序输出。

代码

#include<iostream>constintN=1e4;usingnamespacestd;intmain(){inta[N],size=1,n;a[0]=1;cin>>n;while(n--){intt=0;for(inti=0;i<size;i++){t+=a[i]*2;a[i]=t%10;t/=10;}if(t)a[size++]=t;}for(inti=size-1;i>=0;i--)cout<<a[i];cout<<endl;return0;}

优化

我们发现代码里面采用了 while(n–)，当 n 非常大的时候，可能会超时，所以我们想到了快速幂来进行优化，所谓快速幂，其实是巧妙地利用二进制分解指数，举个很简单的例子，比如说计算 2⁵，我们将 5变换为1+4，那么就是计算2¹⁺⁴，也就是2¹⁰¹，计算变成了1 * 2⁰+ 0 * 2¹+ 1 * 2²。

1. 把指数n拆成二进制（比如 n=5=101，对应 2⁵=2¹ × 2⁴）；
2. 维护一个大整数（数组存储）表示当前的 “平方项”（初始为 2¹）；
3. 遍历 n 的二进制位，若当前位为 1，则把结果（初始为 1）乘以这个平方项；
4. 每轮循环把平方项自身平方（比如 2¹→2²→2⁴→2⁸…），直到处理完所有二进制位。

另外一个版本

1. 拆解指数：把要计算的指数 n（比如 10）拆成「最大的 2 的幂次之和」（10=8+2），而非逐次减 1；
2. 批量计算：每个 2 的幂次对应 “批量乘 2^step 次”（比如 step=8 就一次性乘 8 次 2），减少循环判断的次数；
3. 高效循环：循环次数从原来的 n 次（比如 10 次）骤降到 log₂n 次（比如 10 次→2 次），这是快速幂 “快” 的核心。

快速幂模板

求 m^k mod p，时间复杂度O(logk)。intqmi(intm,intk,intp){intres=1%p,t=m;while(k){if(k&1)res=res*t%p;t=t*t%p;k>>=1;}returnres;}

优化后代码

#include<iostream>constintN=1e4;voidmulti(inta[],int&size){intt=0;for(inti=0;i<size;i++){t+=a[i]*2;a[i]=t%10;t/=10;}if(t)a[size++]=t;}usingnamespacestd;intmain(){inta[N],size=1,n;a[0]=1;cin>>n;while(n){intstep=1;while(step*2<=n)step*=2;for(inti=0;i<step;i++)multi(a,size);n-=step;}for(inti=size-1;i>=0;i--)cout<<a[i];cout<<endl;return0;}

变式

计算 bⁿ，n <= 10000 。

变式基本代码

#include<iostream>constintN=1e4;usingnamespacestd;intmain(){inta[N],size=1,n,b;a[0]=1;cin>>b>>n;while(n--){intt=0;for(inti=0;i<size;i++){t+=a[i]*b;a[i]=t%10;t/=10;}if(t)a[size++]=t;}for(inti=size-1;i>=0;i--)cout<<a[i];cout<<endl;return0;}

变式优化代码

#include<iostream>constintN=1e4;voidmulti(inta[],intb,int&size){intt=0;for(inti=0;i<size;i++){t+=a[i]*b;a[i]=t%10;t/=10;}if(t)a[size++]=t;}usingnamespacestd;intmain(){inta[N],size=1,n,b;a[0]=1;cin>>b>>n;while(n){intstep=1;while(step*2<=n)step*=2;for(inti=0;i<step;i++)multi(a,b,size);n-=step;}for(inti=size-1;i>=0;i--)cout<<a[i];cout<<endl;return0;}