首页 > 代码库 > 快速幂算法
快速幂算法
快速幂就是快速算出某个数的多少次幂a^b
普通方法O(n)不解释:
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstdlib> 5 #include<iomanip> 6 #include<algorithm> 7 using namespace std; 8 int main() 9 {10 int a=10,b=5,m;11 m=a;12 a=1;13 while(b>0)14 {15 if(b&1)a=a*m;16 b>>=1;17 m=m*m;18 }19 cout<<a;20 return 0;21 }
快速幂O(log?N):
把b转化成二进制
例如： 10的而二进制为1010
并且10=2^1+2^3
因此a^10=a^(2^1)*a^(2^3) 代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstdlib> 5 #include<iomanip> 6 #include<algorithm> 7 using namespace std; 8 int main() 9 {10 int a=10,b=5,m;11 m=a;12 a=1;13 while(b>0)14 {15 if(b&1)a=a*m;16 b>>=1;17 m=m*m;18 }19 cout<<a;20 return 0;21 }
快速幂算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。