Road Map

快速幂

快速求 a^k \bmod p 的结果；时间复杂度 为 $O(logk)$

原理

预处理得到

a^{2^0} \bmod p

a^{2^1} \bmod p

a^{2^2} \bmod p

...

a^{2^{logk}} \bmod p

可以把 $a^k$ 看做是 $a^{2^{x_1}} \times a^{2^{x_2}} \times a^{2^{x_3}} \times ...$

也就是把 $k$ 分解成 $2^{x_1} + 2^{x_2} + 2^{x_3} + ... $ 的形式

代码实现

求a^k \bmod p

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