模板||快速幂
2019-05-16 23:54:34来源:博客园 阅读 ()
有那么一种算法可以让计算a^b变得更快,那就是快速幂。如果直接暴力计算的话需要计算b次。时间蛮长的。
题目描述:
输入a,b.(a,b为整数)计算a^b。
输入输出格式
输入格式:
两个整数a、b。.
输出格式:
输出“a^b=s”
s为运算结果
前提:你需要了解二进制,十进制。位运算的知识(当然也可以没有,万事皆可模拟。)
没有位运算的:
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<iomanip> #include<queue> #include<cmath> using namespace std; char e[10001]; int cd; long long quickpow(long long a,char b[]) { long long ans=1,base=a; while(cd!=-1) { if(int(b[cd])!=0) ans*=base;//最后一位是1的话。 base*=base; cd--;//抹去最后一位。 } return ans; } void zh(long long a) { char zs[10001]; int sum=0; while(a!=0) { zs[sum]=a%2; a/=2; sum++; } sum--; int js=sum; cd=sum;//转换为二进制后的最后一个元素的位置。如(10)10
=(1010)2
最后一个元素的位置为三。 for(int i=0;i<=sum;++i) { e[js]=zs[i]; js--; } } int main() { long long a,b; cin>>a>>b; zh(b);//将b转换为二进制。 cout<<quickpow(a,e); return 0; }
代码:
//省略...... long long quickpow(long long a,long long b) { long long ans=1,base=a; while(b!=0) { if(b&1!=0) ans*=base; base*=base; b>>=1; //将b的二进制数向右移一位(相当于将b的二进制数的最后一位抹掉。) } return ans; }
PS:不用位运算的代码当指数为零时需要特判!
注意:因为是乘方运算所以很有可能会爆long long!
input:
2 11
output:
2048
先讲一下(&、>>)位运算.
&:‘&’叫做按位与。作用:把参与运算的两个数对应的二进制相与,只有对应的二进制均为1时,结果(应该也是二进制的形式)的对应位才为1,否则为0。
>>:'>>'叫做右移。作用:把“>>”左边的运算数的各二进制位全部右移若干位(“>>”右边的那个数)。
以此样例讲一下吧。
(11)10=(1011)2。
如何将二进制转换为十进制那?
酱紫,1*20 +1*21 (+0*22) +1*23。
∴211=2(1*20 +1*21 (+0*22) +1*23)。
小学我们学过 an*am=an+m。
∴211=21*22*28。
快速幂就是这样计算的!
模拟一下样例:
ans=1,base=2。
11的二进制数为1011,不为0 进行循环直到为0。
1011的最后一位为1,ans*base。
若不为1,就不进行ans*base。
base*base,就是由2变成了4(2^2)。
1011抹去最后一位直到为0.
就是酱紫。
//转载来自这里
原文链接:https://www.cnblogs.com/skkyk/p/10872266.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 单调队列模板【附例题】 2020-05-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash