首页 > 代码库 > 快速幂[分治]
快速幂[分治]
快速幂
——!x^n+y^n=z^n
我们在编写程序中常常会碰到求解a^p 的情况,这时候如果只是简单的遍历一遍会浪费很多时间,这时候我们就需要快速幂了。
其实快速幂的操作非常简单,比如我们要求a^p,我们只需求 a^(p/2),再平方就行了,如果p为奇数,那我们只需在乘一个p即可。
在此主要介绍一种用位运算处理的快速幂:
我们考虑 a^p ,如果我们用二进制来看待p 假设为(10101)2,即为1+0*2^1+1*2^2...。意思就是说我可以这样来表示:
a^(10000)2*a^(100)2*...
我们注意到只需把这个二进制位有1的部分乘入答案即可,并且a^(1<<i)=(a^(1<<(i-1)))^2,那么利用这一特性我们就能简洁漂亮地得到一种快速幂的写法。
附上Lowbee的代码
int fpow(int a,int p){ int res=1,base=a; while(p>0){ if(p&1) res*=base; base*=base; p>>=1; } return res;}
快速幂[分治]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。