快速幂

快速幂

快速的求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;
}