快速幂

发表于 分类于 阅读次数：
本文字数： 177 阅读时长 ≈ 1 分钟

快速幂

快速的求a^k mod p

20220129211626

1
2
3
4
5
6
7
8
9
10
11
12
13
14
求 m^k mod p，时间复杂度 O(logk)。

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