本博文源于C语言求解快速幂的问题，快速幂是一种基于二分法的思想，常称为二分幂，快速幂基于以上事实：
-
如果b是奇数，那么有
ab
=
a
∗
a
b
−
1
a^b=a*a^{b-1}
a
b
=
a
∗
a
b
−
1
-
如果b是偶数，那么有
ab
=
a
b
/
2
∗
a
b
/
2
a^b=a^{b/2}*a^{b/2}
a
b
=
a
b
/
2
∗
a
b
/
2
举个例子，如果需要求
2
10
2^{10}
2
1
0
-
对于
210
2^{10}
2
1
0
来说，由于幂次10为偶数，因此需要先求
25
2^{5}
2
5
,然后有
210
2^{10}
2
1
0
=
25
∗
2
5
2^{5}*2^{5}
2
5
∗
2
5
-
对于
25
2^{5}
2
5
来说，由于幂次5为偶数，因此需要先求
24
2^{4}
2
4
,然后有
25
2^{5}
2
5
=
2∗
2
4
2*2^{4}
2
∗
2
4
-
对于
24
2^{4}
2
4
来说，由于幂次4为偶数，因此需要先求
22
2^{2}
2
2
,然后有
24
2^{4}
2
4
=
22
∗
2
2
2^{2}*2^{2}
2
2
∗
2
2
-
对于
22
2^{2}
2
2
来说，由于幂次2为偶数，因此需要先求
21
2^{1}
2
1
,然后有
22
2^{2}
2
2
=
21
∗
2
1
2^{1}*2^{1}
2
1
∗
2
1
-
对于
21
2^{1}
2
1
来说，由于幂次1为偶数，因此需要先求
20
2^{0}
2
0
,然后有
21
2^{1}
2
1
=
2∗
2
0
2*2^{0}
2
∗
2
0
-
20
2^{0}
2
0
=1,然后从下往上依次回退计算即可。
#include<stdio.h>
typedef long long LL;
LL binaryPow(LL a,LL b,LL m){
if(b==0) return 1;//如果b为0，那么a^0 = 1
//b为奇数，转化为b-1
if(b%2==1) return a* binaryPow(a,b-1,m)%m;
else{
//b偶数,转化为b/2
LL mul = binaryPow(a,b/2,m);
return mul * mul % m;
}
}
int main()
{
LL res = binaryPow(2,3,3);
printf("%ld",res);
return 0;
}
也可以将上面的进行位运算，代码就变成这样了。
LL binaryPow(LL a,LL b,LL m){
LL ans = 1;
while(b>0){
if(b&1){
//如果b的二进制末尾为1，(也可以写成if(b%2))
ans = ans * a % m;//令ans累计上a
}
a = a*a%m;//令a平方
b>>=1;//将b的二进制右移1位，即b=b>>1或b=b/2;
}
return ans;
}