# Road Map
# 快速幂
快速求 a^k \bmod p 的结果;时间复杂度 为
# 原理
预处理得到
a^{2^0} \bmod p
a^{2^1} \bmod p
a^{2^2} \bmod p
...
a^{2^{logk}} \bmod p
可以把 看做是
也就是把 分解成 $2^{x_1} + 2^{x_2} + 2^{x_3} + ... $ 的形式
# 代码实现
求a^k \bmod p
int qmi(int a, int k, int p)
{
int res = 1 % p;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11