快速幂（c++，超级详细）

快速幂

如果我们打算求a^b, 我们可能会写一个for循环，乘以b次a，时间复杂度为O(b)

当b比较小的时候还可以运用，但是当b很大，比如b=1000000,此时时间复杂度就显然很高了，我们需要对其进行优化 ———快速幂

开始之前，先说两个前置知识：

1 二进制构成数字

众所周知，每个十进制数都可以由唯一的二进制数表示

例如：13的 二进制表示为 1101 即表示为 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0
 即13可以由8+4+1组成
   
1
2
3

我们不难发现，每一个十进制数都由其对应的二进制数，那么每一个十进制数都可以有1 2 4 8 32 64 … 等这种二的次方数相加得到，并且每一种数只能取1个或0个

再例如 9，其二进制为1001 ， 8+1=9 ，即由1个8和1个1相加得到9

2 位运算

& 运算符可以直接对二进制进行操作，1 & 1 = 1，1 & 0 =0， 0 & 1 = 0， 0 & 0 = 0，
  
1
2

我们不难发现只有1&1才是1，根据这个思想，我们可以判断当前数字的二进制是否有1

>> 右移运算符，可以删掉末尾二进制数
    例如5 的二进制为101 5>>1 ==2 2的二进制为10 删掉了原先末尾的1
    再例如6的二进制为110 6>>1==3 3的二进制为11 删掉了末尾的0
1
2
3

其实不难发现，右移1就是乘以2，>>n,就是乘以2^n次方

结合&和>>

我们可以写个循环。逐渐判断每一位是否是1

int b  = 13;
int res = 0;//统计b二进制1的数目
while(b){
    if(b&1==1)res++; //如果当前位为1，就统计+1
    b = b>>1;//将末尾位删掉
}
1
2
3
4
5
6

3 快速幂算法(不取余版)

学完前面两个前置知识，我相信再学习 快速幂 将会很简单

首先假设我们要求5^13次方

13的二进制为1101 所以13 = 8+4+1；

即5^13 = 5^1 * 5^4 * 5^8

ps: 幂运算可是高中数学学的 a^(m+n） = a^m * a^n;

有这些知识我们就能直接看代码了

要是还有疑惑点，看代码注释也能看懂

long long quick_pow(long long a,long long b){
    //计算a^b次方
    long long res = 1;//用res保存答案
    //当b变成0后就可以停止循环了
    while(b){
        if(b & 1) ans*=a;//如果b当前二进制为1就要乘上这个数
        b>>=1; //将b末尾的二进制数删掉
        a*=a; // 将a乘以自己进行翻倍
        //比如，开始a==5,接下来a = 5^2,a=5^4,a=5^8,a=5^16....
        //通过遍历每个在范围内的2的次方数来更新a
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

4 取模版快速幂

快速幂只有五行代码，是不是很简单呢

不过别急，上面的快速幂是最原始版的，一般不是很常用，当a本身非常大时，如果a*a可能 long long 都给爆掉了，所以我们一般会采取取模的方式进行运算

前置知识 (a *b *c *d )%p = (((a *b)%p *c)%p *d)%p

即每次乘以下个数前可以先取模，这样最后答案不变，所以我们的代码可以进行优化了

LL quick_pow(LL a, LL b, LL p){ //LL是long long 的缩写
  //p是要对取模的数字
    LL ans = 1;
    while(b){
        if(b & 1)ans =(ans*a)%p;
        b >>= 1;
        a = (a*a) % p;
    }
    return ans;
    
}
1
2
3
4
5
6
7
8
9
10
11

原题链接：875. 快速幂 - AcWing题库

完整代码

#include

using namespace std;
typedef long long LL;
LL n;
LL quick_pow(LL a, LL b, LL p){
    LL ans = 1;
    while(b){
        if(b & 1)ans =(ans*a)%p;
        b >>= 1;
        a = (a*a) % p;
    }
    return ans;
    
}
int main(){
    cin>>n;
     while(n--){
         LL a,b,p;
         cin>>a>>b>>p;
         cout<<quick_pow(a,b,p)<<endl;
     }
     return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24