首页 > 代码库 > 快速幂取模算法
快速幂取模算法
快速幂顾名思义，就是快速算某个数的多少次幂。其时间复杂度为 O(log?N)， 与朴素的O(N)相比效率有了极大的提高。——bybaidu
原理：
以求a的b次方来介绍
把b转换成二进制数。
该二进制数第i位的权为
。
例如：
11的二进制是 1011
11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1
因此，我们将a¹¹转化为算
。
实现：
快速幂可以用位运算这个强大的工具实现。
代码比较：
常规求幂
intpow1(int a,int b){ int r=1; while(b--) r*=a; return r;}
二分求幂（一般）
intpow2(int a,int b){ int r=1,base=a; while(b!=0) { if(b%2) r*=base; base*=base; b/=2; } return r;}
快速求幂（位操作）
intpow3(int a,int b){ int r=1,base=a; while(b!=0) { if(b&1) r*=base; base*=base; b>>=1; } return r;}
其中二分求幂与快速求幂都是利用了二进制数的思想。
蒙哥马利快速幂取模算法，简单漂亮
int pow3(int a,int b,int c){ int ans=1; a=a%c; while(b!=0) { if(b&1) ans=(ans*a)%c; a=(a*a)%c; b>>=1; } return ans;}
快速幂取模算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。