算法簡(jiǎn)介
快速冪取模算法是在o( logn )的時(shí)間內(nèi)求得 a ^ b % n的值
先證明結(jié)論：
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時(shí) a ^ b = ( a ^ ( b / 2 ) ) ^ 2 * a;
b & 1 == 0時(shí) 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;
}
byene.jpg
