快速幂算法
快速幂
快速幂算法——可迅速计算出
1. 当b为偶数时,可将
2. 当b为奇数时,可将
继续按这个规则进行迭代。
//快速幂
LL pow_m(LL a,LL n,LL MOD)
{
LL ret=1;
LL tmp=a%MOD;
while(n)
{
if(n&1)
{
ret=(ret*tmp)%MOD;
}
tmp=tmp*tmp%MOD;
n>>=1;
}
return ret;
}