快速幂

原理

  可以在log(k)的时间复杂度下计算a^k (mod p)的值。将k以2进制展开，其中的每一个1相当于乘以a^(2^m)。

假设 k的二进制表示为10010101:

$$a^k = a^{2^0} * a^{2^2} * a^{2^4} * a^{2^7}$$

模板

LL qmi(LL a, LL k, LL p)
{
    LL res = 1;
    while (k)
    {
        if (k & 1)
        {
            res = res * a % p;
            a = a * a % p;
        }
        k >>= 1;
    }

    return res;
}

例题

AW.875 快速幂（简单）

AW.876 快速幂求逆元（简单）

快速幂求逆元用到了费马小定理，是扩展欧几里得定理的一个特例