快速幂

http://baike.baidu.com/view/4533005.htm
常规求幂

1 2 3 4 5 6 7

int pow1( int a, int b ) {     int r = 1;     while( b-- )         r *= a;     return r; }

二分求幂（一般）

1 2 3 4 5 6 7 8 9 10 11 12

int pow2( int a, int b ) {     int r = 1, base = a;     while( b != 0 )     {         if( b % 2 )             r *= base;         base *= base;         b /= 2;     }     return r; }

快速求幂（位操作）

1 2 3 4 5 6 7 8 9 10 11 12

int pow3( int a, int b ) {     int r = 1, base = a;     while( b != 0 )     {         if( b & 1 )             r *= base;         base *= base;         b >>= 1;     }     return r; }

递归版本快速幂

int power(int a,int b){

   6:     if(b==1)return a;

   7:     int tpans=power(a,b>>1);

   8:     return tpans*tpans*((b&1)?a:1); 

   9: }

快速求幂（更高效率的位运算法）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

int pow4(int x, int n) {     int result;     if (n == 0)         return 1;     else     {         while ((n & 1) == 0)         {             n >>= 1;             x *= x;         }     }     result = x;     n >>= 1;     while (n != 0)     {            x *= x;         if ((n & 1) != 0)             result *= x;         n >>= 1;     }     return result; }

http://www.cnblogs.com/archimedes/p/3637479.html

int PowerMod(int a, int b, int c)
{
    int ans = 1;
    a = a % c;
    while(b>0) {
        if(b % 2 = = 1)
        ans = (ans * a) % c;
        b = b/2;
        a = (a * a) % c;
    }
    return ans;
}

本算法的时间复杂度为O（logb），能在几乎所有的程序设计（竞赛）过程中通过，是目前最常用的算法之一。

快速幂取模算法

在Miller Rabbin测试素数，就用到了快速幂取模的思想。这里总结下。
求a^b%c（这就是著名的RSA公钥的加密方法），当a,b很大时，直接求解这个问题不太可能 

算法1：利用公式a*b%c=((a%c)*b)%c,这样每一步都进行这种处理，这就解决了a^b可能太大存不下的问题，但这个算法的时间复杂度依然没有得到优化

1. int modexp_simple(int a,int b,int n)       
2. {      
3.     int ret = 1;  
4.     while (b--)  
5.     {  
6.         ret = a * ret % n;  
7.     }  
8.     return ret;  
9. } 

算法2：另一种算法利用了二分的思想，可以达到O(logn)。
可以把b按二进制展开为：b = p(n)*2^n  +  p(n-1)*2^(n-1)  +…+   p(1)*2  +  p(0)
其中p(i) (0<=i<=n)为 0 或 1

这样 a^b =  a^ (p(n)*2^n  +  p(n-1)*2^(n-1)  +...+  p(1)*2  +  p(0))
               =  a^(p(n)*2^n)  *  a^(p(n-1)*2^(n-1))  *...*  a^(p(1)*2)  *  a^p(0)
对于p(i)=0的情况, a^（p(i) * 2^(i-1) ） =  a^0  =  1,不用处理
我们要考虑的仅仅是p(i)=1的情况
化简：a^(2^i)  = a^(2^(i-1)  * 2) = (  a^(  p(i)  *  2^(i-1)  )  )^2（这里很重要！！具体请参阅秦九韶算法：http://baike.baidu.com/view/1431260.htm）
非递归优化 

1. int modexp(int a,int b,int n)     
2. {     
3.     int ret=1;     
4.     int tmp=a;     
5.     while(b)     
6.     {     
7.        //基数存在     
8.        if(b&0x1) ret=ret*tmp%n;     
9.        tmp=tmp*tmp%n;     
10.        b>>=1;     
11.     }     
12.     return ret;     
13. }

递归

1. int modexp_recursion(int a,int b,int n)       
2. {      
3.     int t = 1;  
4.   
5.     if (b == 0)  
6.         return 1;  
7.   
8.     if (b == 1)  
9.          return a%n;  
10.   
11.     t = modexp_recursion(a, b>>1, n);  
12.   
13.     t = t*t % n;  
14.   
15.     if (b&0x1)  
16.     {      
17.         t = t*a % n;  
18.     }  
19.   
20.     return t;  
21.  }