首页 > 代码库 > 快速幂
快速幂
快速幂
如何快速计算nm?我们采用从特殊到一般的数学思想:
假设n=2,m=10
直接算的结果是2*2*2*2*...*2 计算了10次
快速幂的思想是将m二进制化
210=4*16*16 计算了3次
同理可得,nm用快速幂来计算的过程是使底数不断倍增,指数倍减,达到时间上的优化:O(N)->O(logN)
模板:
1 //读者可以根据自己的需要,更改返回值的类型 2 long long qpow(long long d){ 3 long long a=10,ans=1;//我们假设是求10^d 4 while(d>0){ 5 if(d&1)ans=(ans*a)%n;//当指数倍减至奇数时,和答案相乘 6 a=(a*a)%n;//底数倍增 7 d>>=1;//指数倍减 8 } 9 return ans;//返回答案10 }11 //根据二进制的拆分,时间复杂度是对数级别的
快速幂
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。