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;
}
代码解析
由于快速幂力求快速， 因此涉及位运算
n&1
&符号代表按位与，1的二进制最后一位为1，其余为零。如果一个数为奇数，那么最后一位必为1，其余位必为0，所以得出结果为1。如果是偶数的话，最后一位必然为0，其余位与0与运算必为0，所以结果为0，这样就可以起到判断奇数偶数的效果。
k >>= 1
全部位右移一位，最低位直接舍去。
实际上就是除以2
int qmi(int m, int k, int p)
{
int res = 1 % p, t = m;
while (k)
{
//若k为奇数， 无法继续降幂， 进行计算， 计算后， k变为k-1
if (k&1) res = res * t % p;
// 升底数
t = t * t % p;
// 降幂数
k >>= 1;
}
return res;
}
实例
以
2
10
为
例
2^{10}为例
210为例
快速幂
2
20
=
2
2
∗
10
=
4
10
=
4
2
∗
5
=
1
6
5
=
16
∗
1
6
4
=
25
6
4
=
25
6
2
∗
2
=
6553
6
2
=
4294967296
2^{20} = 2^{2*{10}} = 4^{10} =4^{{2*5}}=16^5=16*16 ^4= 256^4 = 256^{2*2}=65536^2=4294967296
220=22∗10=410=42∗5=165=16∗164=2564=2562∗2=655362=4294967296
pow暴力
2
∗
2
∗
2
…
…
2
∗
2
∗
2
2*2*2……2*2*2
2∗2∗2……2∗2∗2
