一、定义
快速幂顾名思义,就是快速算某个数的多少次幂。
其时间复杂度为 O(log2N), 与朴素的O(N)相比效率有了极大的提高。
以下以求a的b次方来介绍
二、原理
把b转换成2进制数
该2进制数第i位的权为(2^(i-1))
例如
a^11=a^(2^0+2^1+2^3)
11的二进制是1 0 1 1
11 = 2^3*1 + 2^2*0 + 2^1*1 + 2^0*1
因此,我们将a^11转化为算a^(2^0)*a^(2^1)*a^(2^3)
int Fast_Power(int a, int b){
int ans = 1;
while(b>0){
if(b % 2 == 1)
ans *= a;
b >>= 1;
a *= a;
}
return ans;
}
由于指数函数是爆炸增长的函数,所以很有可能会爆掉int的范围,一般题目会要求mod某个数c;
int PowerMod(int a, int b, int c){
int ans = 1;
a = a % c;
while(b>0){
if(b % 2 == 1)
ans = (ans * a) % c;
b >>= 1;
a = (a * a) % c;
}
return ans;
}
JAVA版本一
private static int Fast_Power(int a, int b) {
int s = 1;
while (b > 0) {
if (b % 2 == 1) {//b=b>>1保证了在最后一步肯定会执行该if判断
s = s * a;
}
a = a * a;
b = b >> 1;
}
return s;
}
三、例题
http://acm.hdu.edu.cn/showproblem.php?pid=1420(题解:https://blog.csdn.net/weixin_43272781/article/details/88952920)
http://acm.hdu.edu.cn/showproblem.php?pid=1061(题解:https://blog.csdn.net/weixin_43272781/article/details/88953103)