求$m^k\%p$，时间复杂度O(logk).
C++ 版本模板
1
2
3
4
5
6
7
8
9
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;
}
求$m^k\%p$，时间复杂度O(logk).
1
2
3
4
5
6
7
8
9
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;
}
