快速幂取模
求一个数的幂对另一个数的模的运算,称为模取幂。普通的计算方法很容易超出空间限制和时间限制。例如:
求a ^ b mod(n), 利用模运算法则 (a*b)%n = (a%n)(b%n)%n, 可以大大提高计算的效率。
1:将b化为2进制,则由高位到低位为:Bn,B(n-1),……B1,B0.每一位Bi都只能是0或者1;
2: 因此a^b可以分解为( a^(2^n) )* (a^(2^(n-1) ) )……( a^2)*a;当然这个式子并不完全正确,只有当从右数的第k位B(k+1)为1的时候再要在式子中乘上一个( a^2^(k-1) ),如果为B(k+1) 0当然就不需要乘。 由该式,可以由a递推出所有的a^2^(k-1);
3: a^(2^k)%c = ( (a^(2^(k-1))%c) * a^(2^(k-1))) %c;
4:再把所有满足B(i)=1的a^(2^i)%c按照步骤3一样乘起来再%c就是结果, 即二进制扫描从最低位一直扫描到最高位;
LL mulmod( LL a, LL b , LL p )
{
LL d =1;
a = a%p;
while( b>0 )
{
if(b&1)
d = (d*a)%p;
a = (a*a)%p;
b>>=1;
}
return d;
}
在这段代码中 ,a在递归的推导a^(2^k)%c。d则将目前求出的a^(2^k)%c和之前的累积求积再取模。
本代码和思路都参考他人的博客。仅代表记录学习过程。