快速幂取模算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了快速幂取模算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1381字,纯文字阅读大概需要2分钟。
内容图文
![快速幂取模算法](/upload/InfoBanner/zyjiaocheng/843/51edd3d7265a4082be1a42c49af33fdc.jpg)
1 //base是底数,index是指数,mode是取模数,result是记录结果。 2 int result = 1; 3 base = base % mode; 4 for(int i = 1; i <= index; ++i) 5 { 6 result = result * a; 7 } 8 result = result % mode;这是直接利用引理写出的代码,它的效果不是很理想,优化度也不高。我们是否可以继续拆分呢? 下面是我目前已知的最优的拆分合并方法。 2,我们可以看到,对于7*7*7*7*7*7,即7^6,与49*49*49,即49^3,结果是一样的,我们在可接受的范围内合并了底数,又优化了指数,这样我们不停的进行循环合并,就可以成功的写出快速幂算法。 如果指数是奇数,那就在偶数算法的基础上,把多余的一个数跳出来,剩下的与偶数算法一样,所以,这里多了一个奇偶判断。
1 //base是底数,index是指数,mode是取模数,result是记录结果。 2 typedef long long ll; 3 ll Mode(ll base, ll index, ll mode) 4 { 5 ll result = 1; 6 while(index) 7 { 8 if(index & 1) 9 { 10 result = (result * base) % mode; 11 index--; 12 } 13 index >>= 1; 14 base = (base * base) % mode; 15 } 16 return result; 17 }
这就是快速幂算法。
内容总结
以上是互联网集市为您收集整理的快速幂取模算法全部内容,希望文章能够帮你解决快速幂取模算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。