快速幂(Fast_Power)
2024-09-30 07:00:55
定义
快速幂顾名思义，就是快速算某个数的多少次幂。
其时间复杂度为 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)[1]
int Fast_Power(int a, int b){
int ans = ;
while(b>){
if(b % == )
ans *= a;
b >>= ;
a *= a;
}
return ans;
}
由于指数函数是爆炸增长的函数，所以很有可能会爆掉int的范围，一般题目会要求mod某个数c；
int PowerMod(int a, int b, int c){
int ans = ;
a = a % c;
while(b>){
if(b % == )
ans = (ans * a) % c;
b >>= ;
a = (a * a) % c;
}
return ans;
}
JAVA版本一
private static int Fast_Power(int a, int b) {
int s = ;
while (b > ) {
if (b % == ) {//b=b>>1保证了在最后一步肯定会执行该if判断
s = s * a;
}
a = a * a;
b = b >> ;
}
return s;
}
最新文章
- mysql优化记录
- frame里的链接跳转
- 瞎BB
- EC6 map 和 set
- apache http client vs urlconnection
- c# 读取IntPtr 中的数据 z
- delphi array应用 DayOfWeek星期几判断
- DebugView图文教程
- 【Tcpcopy】离线回放功能
- HTML——表格table标签，tr或者td
- 机器学习实战：数据预处理之独热编码（One-Hot Encoding）
- Windows 下多线程编程技术
- JAVA Web学习篇--Servlet
- C#中Predicate的一点理解
- Linux 文件名匹配
- hl7 java 解析
- Java描述语言、国家和地理的类——Locale
- Uva 10550 Combination Lock
- selenium java ，执行js改变页面
- python成长之路六-函数的初识