快速幂（幂运算取模的logn算法）

以下以求a的b次方来介绍

 

　　　　把b转换成二进制数

 

　　　　该二进制数第i位的权为

　　　　　　　　　　　　　　　　　　　　　　

　　　　例如

　　　　　　　　　　　　　　　　　　

　　　　11的二进制是1011

　　　　　　　　　　　　　　11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1

　　　　因此，我们将a¹¹转化为算

 　　　　　　　　　　　　　　　　　　

　　　　

　　　　对于　　　　　　　　　　　　令A[0]=a^(2^0)*1　　A[1]=a^(2^1)*1　　　A[2]=a^(2^2)*0　　A[3]=a^(2^3)*1

　　　　

　　　　可以看出A[N]的前半部分是A[N-1]前半部分的平方倍　　则可以一直循环推(a^(2^k))^2,从右到左依次取b二进制数的位数  如果是0则不乘入答案 如果是1则乘入答案（无论乘入不乘入 一直将a的平方推下去（就前边辣个））

 　　　　直到b为0跳出循环

　　　　

　　　　必备的知识

 

　　　　对于取模运算：(a*b)%c=(a%c)*(b%c)%c 成立

　　　　//实际上

　　　　　　(a +  b) % p = (a%p +  b%p) %p　　　　　　

　　　　　　(a  -  b) % p = (a%p  -  b%p) %p  也成立

　　　　　　但是除法不成立 可以举例证明

　　　　位运算  <<k  左移二进制数 相当于乘上2^k 

　　　　　　　  >>k  右移二进制数　 相当于除2^k

　　　　&且 1&1=1　　　　　　　　| 或    1|1=1　

　　　　　　1&0=0　　　　　　　　　　  1|0=1 

　　　　　　0&1=0　　　　　　　　　　  0|1=1 

　　　　　　0&0=0　　　　　　　　　　  0|0=0 

　　　　　　

　　　　　　

//实现代码
//mod  c

int quick(int a,int b,int c)  
{  
    int ans=1;   //记录结果  
    a=a%c;   //预处理，使得a处于c的数据范围之下  
    while(b!=0)  
    {  
        if(b&1) ans=(ans*a)%c;   //如果b的二进制位不是0，那么我们的结果是要参与运算的  
        b>>=1;    //二进制的移位操作，相当于每次除以2，用二进制看，就是我们不断的遍历b的二进制位  
        a=(a*a)%c;   //不断的加倍  
    }  
    return ans;  
}