快速幂为什么这么快

快速幂为什么这么快

在解决一些数学问题时经常用到快速幂算法，自己有过这样的疑问，快速幂为什么这么快？现在干脆把它写下来。

代码：

typedef long long LL;LL power(int a,int p){ LL ans=1,temp=a; while(p){ if(p&1) ans=ans*temp; temp=temp*temp; p>>=1; } return ans;}

快速幂充分利用了二进制的特点（非0即1），把十进制转成二进制表达后再展开，ans对于每一位的当前结果要么乘要么不乘，把原本长度是p的循环变成了长度是p二进制位数（log2(n) )的循环。

举例说明：

已知这样一个事实：

有了它，就可以由前一位二进制幂结果推出后一位二进制幂结果，对于每一位二进制幂结果由0和1决定是否乘于ans(0也可以看做给ans乘上了1）。

如此，长度是11的循环变成了长度是4的循环。

对于p很大的情况，此算法的”快“会充分的体现。

而快速幂取模的算法则因为

的成立，加上取模就能使用。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。