快速幂

原理

快速幂原理，利用指数的二进制，只需循环计算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;
}