快速幂算法的理解
浏览数：21 /
时间：2015年06月08日
首先给出代码：
#include <iostream>
using namespace std;
//计算a^bmodn
int modexp(int a,int b,int n)
{
int ret=1;
int tmp=a;
while(b)
{
if(b&1)
ret=ret*tmp%n;
tmp=tmp*tmp%n;
b>>=1;
}
return ret;
}
int main()
{
cout<<modexp(2,10,3)<<endl;
return 0;
} 接下来进行讲解,快速幂算法，就是快速求 x^n mod (m) 的快速算法。
比如：
计算 12996^227 mod 37909
设m = 37909 ， b = 12996, 令a = 1, 将227二进制表示为：227 = 1 + 2 + 2^5 + 2^ 6 + 2^7;
依次计算 12996^227 = 12996 + 12996^2 + 12996^2^5 + 12996^2^ 6 + 12996^2^7;
运用二进制操作,也就是二分的思想,可以达到O(logn)。二进制扫描从最高位一直扫描到最低位。
运用上面的例子：
if(227&1) //也就是说存在2的某次幂不为0,所以需要计算;
………………
227>>=1 //右移一位，继续检查。郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
