分类
Level5

倍增与快速幂

倍增算法，顾名思义，就是成2倍的增长。
倍增主要用途 是为了查找单调数据组中某一数值。比如：在一个数组a {2,5,7,11,19} 中查找最大的小于12的数字。
朴素做法：从第一个数开始，一个一个往后枚举，查找。
二分做法：每次将数列分割一半判断，并且进一步查找子区间。
倍增做法：设定一个增长长度 p 和已确定长度 l，现在要确定 a[l+p] 是否满足条件，若满足条件（比12小），则 p 成2倍增长；否则 p 缩小范围（试着缩小范围判断条件）。

l=0;  //倍增算法一般比较稳定，时间 O(logn)。
p=1;
while(p){ //如果还能扩增范围(l)就继续
    if(a[l+p]<12){
        l+=p;   //增加已知范围
        p<<=1;  //成倍增长，相当于p*=2
    }else{
        p>>=1;  //缩小范围
    }
}
cout<<a[l];

A的B次方 http://oj.lizi101.com/problem.php?id=1715
粗暴求解：不考虑数据范围，我们可以很容易想到以下的解法：

typedef long long LL;
LL POW(LL a,LL b,LL p){
    LL res=1;
    while(b){
        res=res*a;
        b--;
    }
    return  res%p;
}
看了题目的数据范围，发现这个算法会出现以下两个问题：
1. 程序超时。（b的值达到了10^9）
2. 乘法溢出。（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)
4.由(am)*(an)=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。

计算a45的过程模拟。具体代码(代码一)如下：
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 。还可以推广到任意多个因数因数相乘再取模：(a*b*c)%d=(a%d*b%d*c%d)%d。即任意多个因数相乘再取模等于各因数取模后的乘积再取模。对于上面优化过后的代码，只需每一步都对因数（a）取模，同时对“各因数取模后的乘积” res*a再取模,即可维持模值的正确性。由于每一步都取模，累乘后的值就不会溢出了。（注意符号*和符号%的优先级一样，故从左到右计算表达式）。
具体代码（代码二）如下：

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。（字面上应该要这样理解才合理吧）。即快速幂算法代码如下。
至于代码二，应该叫“快速幂取模算法”更合理吧。我觉得只有把两者区分一下，逐个弄懂，才不至于搞懵了。（很多资料都是直接上最终代码二，使得“求幂”和“取模”冗杂在一起，没有递进的逻辑分析，不容易理解）。
（二）特殊情况&代码模板：
在一些oj上，题目的测试数据可能会是b=0,而p=1的情况（此时res应该为0）。如果按上面的代码二，while循环没有执行则会返回错误值1。