我们知道对于幂运算有: ab%k=(a%k)(b%k)%k
如: 5 * 6 % 4 = (1+4)(2+4)% 4 = 1 * 2 % 4
因为 1 * 4 和 2 * 4 和4 * 4模4都为0
位运算加速
// 求 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;
}
© 著作权归作者所有
举报
发表评论
0/200