第11课快速幂 – 专业青少年编程

题目描述：
求 a 的 b 次方对 p 取模的值，其中 0≤a,b,p≤109 。
输入描述:
三个用空格隔开的整数a,b和p。
输出描述:
一个整数，表示a^b mod p的值。

输入
2 3 9
输出
8

粗暴求解：
不考虑数据范围，我们可以很容易想到以下的解法：

typedef long long LL;
LL POW(LL a,LL b,LL p){
LL res=1;
while(b){
res=res*a;
b--;
}
return  res%p;
}

看了题目的数据范围，发现这个算法会出现以下两个问题：

程序超时。（b的值达到了109）
乘法溢出。（res在累乘的时候可能太大）

如何解决超时问题：
1. 超时原因：指数b过大、累乘的次数过多。故应该从指数b出发，降低累乘的次数。
2. 我们知道任何一个正整数都可以由2的整数次幂相加得到。例如:
7=1+2+4 ，9=1+8 ，11=1+2+8，12=4+8，21=1+4+16。
3. 令a的初始值为A，将a的值不断和自身相乘并不断赋给自身，那么A的指数也恰好为2的整数次幂。具体的迭代过程如下：a=a (初始值) (a==A1)
a=a*a （a==A2）
a=a*a (a==A4)
a=a*a (a==A8)
a=a*a (a==A16)
a=a*a (a==A32)
4. 由(am) *(a n)=a(m+n) 可知，在以上的迭代过程中选择一些固定的a值和res进行累乘，就可以使得res等于Ab次方。
5. 那么要选择哪几次迭代的a值进行累乘呢？我们把b转化成二进制表示，就可以直观地看到b是由哪些2的整数次幂相加得到。例如b等于11，其二进制为(1011)2。故11=20 +21 +23 =1+2+8。A11 =(A1)(A2)(A8) =A(1+2+8) ，即选择A1 、A2 、A8 进行累乘可以得到A11。
6. 判断b&1是否为1可以检测b的二进制的最后一位是否是1。不断将b右移就可以检测b的每一位。
7. 检测b在二进制表示下的每一位，若当前位是1，就把当前的迭代值a累乘。
8. 循环由b- -改为b=b>>1,时间复杂度变为为log2b。

计算a^45的过程模拟：

具体代码如下（记为代码一）：
此做法降低了时间复杂度，但并没有解决溢出的问题。

typedef long long LL;
LL POW(LL a,LL b,LL p){
int res=1;
while(b){       
if（b&1）res=res*a;     / /若b&1==1，就选择当前的迭代值a和res累乘。
a=a*a;                  / /迭代构造a,a是初始值的2的整数次幂
b=b>>1;                / /将b右移一位
}                   / /以上计算得到a^b
return res%p;      / /取模
}

如何解决乘法溢出的问题：
首先引入一个模运算的规律：(a * b) % p = (a % p * b % p) % p 。还可以推广到任意多个因数因数相乘再取模：(abc)%d=(a%db%dc%d)%d。即任意多个因数相乘再取模等于各因数取模后的乘积再取模。对于上面优化过后的代码，只需每一步都对因数（aa）取模，同时对“各因数取模后的乘积”resa再取模,即可维持模值的正确性。由于每一步都取模，累乘后的值就不会溢出了。（注意符号*和符号%的优先级一样，故从左到右计算表达式）。
具体代码如下（记为代码二）：

typedef long long LL;
LL POW(LL a,LL b,LL p){
int res=1;
while(b){       
if（b&1）res=res*a%p;     / /对“各因数取模后的乘积”res*a再取模
a=a*a%p;                 / /对因数(a*a)取模
b=b>>1;                  
}                  
return res;     
}

AC完整代码

#include<iostream>
using namespace std;
typedef long long LL;
LL POW(LL a,LL b,LL p){
 LL res=1%p;  / /应对b=0而p=1的情况特殊情况
 while(b>0){
 if(b&1)  res=res*a%p;
 a=a*a%p;
 b=b>>1;    
 }   
 return res;
}
int main(){
  LL a,b,p;  
  cin>>a>>b>>p;  
  cout<<POW(a,b,p);     
return 0;    
}

总结：
（一）一些说明
严格地说，快速幂算法应该指的是上面解决了时间复杂度的代码一，且代码返回值是res。快速幂只是快速求a^b。（字面上应该要这样理解才合理吧）。即快速幂算法代码如下。
至于代码二，应该叫“快速幂取模算法”更合理吧。我觉得只有把两者区分一下，逐个弄懂，才不至于搞懵了。（很多资料都是直接上最终代码二，使得“求幂”和“取模”冗杂在一起，没有递进的逻辑分析，不容易理解）。

typedef long long LL;
LL POW(LL a,LL b,LL p){
int res=1;
while(b){       
if（b&1）res=res*a;     / /若b&1==1，就选择当前的迭代值a和res累乘。
a=a*a;                  / /迭代构造a,a是初始值的2的整数次幂
b=b>>1;                / /将b右移一位
}                     / /以上计算得到a^b
return res;           / /取模
}

（二）特殊情况&代码模板：
在一些oj上，题目的测试数据可能会是b=0,而p=1的情况（此时res应该为0）。如果按上面的代码二，while循环没有执行则会返回错误值1。

typedef long long LL;
LL POW(LL a,LL b,LL p){
int res=1%p;     / /应对b=0而p=1的情况
while(b){       
if（b&1）res=res*a%p;     / /对“各因数取模后的乘积”res*a再取模
a=a*a%p;                 / /对因数(a*a)取模
b=b>>1;                  
}                  
return res;     
}

文章

倍增法

Level3题解（11-20）

文章