原理
快速幂原理,利用指数的二进制,只需循环计算k的二进制位数次即可。
代码
四则运算中的模运算,中间变量可以取模,结果再最终取模。
//b^k%m 时间复杂度O(logk)
int qmi(int b, int k, int m)
{
b %= m; //根据乘积模运算的性质,每个因子均可mod
int res = 1; //乘积初始化为1
while(k)
{
if (k&1) res = res * b % m;
b = b * b % m; //不取mod也可,取模可防止乘积溢出
k >>= 1; //右移>>
}
return res;
}