快速幂取模算法

算法简介

快速幂取模算法是在o( logn )的时间内求得 a ^ b % n的值

先证明结论：
a*b % c = ( ( a % c ) * ( b % c ) ) % c

证明:
a % c = d ----> a = d + c * x;
b % c = e ----> b = e + c * y;
a * b % c = ( de + cex + cdy + xy*c ^ 2 ) %c = ( de ) %c
即证

a ^ b % n = ( a % n ) ^ b % n;

算法核心

递归:
b & 1 == 1时 a ^ b = ( a ^ ( b / 2 ) ) ^ 2 * a;
b & 1 == 0时 a ^ b = ( a ^ ( b / 2 ) ) ^ 2;

int pow_mod( int a, int b, int n )
{
    int t = 1;
    if( b == 0 ) return 1;
    if( b == 1 ) return a % n ;
    t = pow_mod( a, b >> 1, n );
    t = t * t % n;
    if( b & 1 ) t = t * a % n;
    return t;
}

非递归:
b = p(n)2^n + p(n-1)2^(n-1) +...+ p(1)*2 + p(0)

int pow_mod( int a, int b, int n )
{
   int t = 1, tmp = a % n;
   while( b )
   {
       if( b & 1 ) t = t * tmp % n;
       tmp = tmp * tmp % n;
       b >> = 1;
   }
   return t;
}