幂运算是一种幂的运算，它有一个性质：同底数幂相乘，底数不变，指数相加
求幂运算的朴素做法 O ( k ) O(k) O(k)假设此时我们需要求底为a，指数为k的幂的值，即求 r e s = a k res = a^k res=ak，那么我们很容易想到最直接的做法：令 r e s = 1 res = 1 res=1，让res乘以k次a即可得到答案。
代码：int power(int a,int k){
int res = 1;
while(k --) res *= a;
return res;
}
容易看出，它总共进行了k次运算，因此时间复杂度为 O ( k ) O(k) O(k)
快速幂 O ( l o g k ) O(logk) O(logk)有时候当要求的次方大于一定值时，用朴素做法求幂就会显得效率很低，那么有没有什么方法可以快速求幂呢？
这就需要用到上方的性质：同底数幂相乘，底数不变，指数相加
假设我们需要求
3
7
3^7
37，那么我们可以分为
3
∗
3
∗
3
∗
3
∗
3
∗
3
∗
3
3 * 3 * 3 * 3 * 3 * 3 * 3
3∗3∗3∗3∗3∗3∗3，也可以等于
3
2
∗
3
2
∗
3
2
∗
3
3^2 * 3^2 * 3^2 * 3
32∗32∗32∗3，原因是它们的指数之和为
7
7
7，那么我们就会想到二进制优化
7
=
4
+
2
+
1
=
2
2
+
2
1
+
2
0
=
11
1
2
7 = 4 + 2 + 1 = 2^2 + 2^1 + 2^0 = 111_2
7=4+2+1=22+21+20=1112
于是
3
7
=
3
11
1
2
3^7 = 3^{111_2}
37=31112
因此我们只需要处理出指数k的二进制表示及每个二进制数下的乘数即可。
- 如果k为0，停止运算
- 每当 k k k的最低位数为0时， r e s res res不进行运算，为1时， r e s = r e s ∗ a res = res * a res=res∗a
- 然后将 a = a ∗ a a = a * a a=a∗a(每个二进制数下的乘数)
- 最后 k > > = 1 ( k = k / 2 ) k >>= 1(k = k / 2) k>>=1(k=k/2)
求
3
7
(
3
11
1
2
)
3^7(3^{111_2})
37(31112)：
r
e
s
=
1
res = 1
res=1
k
!
=
0
k != 0
k!=0
k的最低位为1,
r
e
s
=
r
e
s
∗
a
=
1
∗
3
=
3
res = res * a = 1 * 3 = 3
res=res∗a=1∗3=3；
a
=
a
∗
a
=
9
a = a * a = 9
a=a∗a=9
k
>
>
=
1
k >>= 1
k>>=1
k
=
k
/
2
=
3
(
11
1
2
>
>
1
=
=
1
1
2
)
k = k / 2 = 3(111_2 >> 1 == 11_2)
k=k/2=3(1112>>1==112)
k
!
=
0
k != 0
k!=0
k的最低位为1,
r
e
s
=
r
e
s
∗
a
=
3
∗
9
=
27
res = res * a = 3 * 9 = 27
res=res∗a=3∗9=27；
a
=
a
∗
a
=
81
a = a * a = 81
a=a∗a=81
k
>
>
=
1
k >>= 1
k>>=1
(
k
=
k
/
2
=
1
,
(
1
1
2
>
>
1
=
=
1
2
)
)
(k = k / 2 = 1,(11_2 >> 1 == 1_2))
(k=k/2=1,(112>>1==12))
k
!
=
0
k != 0
k!=0
k的最低位为1,
r
e
s
=
r
e
s
∗
a
=
27
∗
81
=
2187
res = res * a = 27 * 81 = 2187
res=res∗a=27∗81=2187；
a
=
a
∗
a
=
6561
a = a * a = 6561
a=a∗a=6561
k
>
>
=
1
k >>= 1
k>>=1
(
k
=
k
/
2
=
0
,
(
1
2
>
>
1
=
=
0
2
)
)
(k = k / 2 = 0,(1_2 >> 1 == 0_2))
(k=k/2=0,(12>>1==02))
k
=
=
0
k == 0
k==0
返回
r
e
s
=
2187
res = 2187
res=2187
int qmi(int a,int k){ // 求a的k次方
int res = 1;
while(k){
if(k & 1) res = res * a;
a = a * a;
k >>= 1;
}
return res;
}
含求模运算的代码
int qmi(int a,int k,int p){ // 求a的k次方模p
int res = 1;
while(k){
if(k & 1) res = (long long)res * a % p;
a = (long long)a * a % p;
k >>= 1;
}
return res;
}
可以看出它只需要进行 l o g k logk logk次运算，因此时间复杂度为 l o g k logk logk
