快速 求幂（ 快速幂)

快速 求幂（ 快速幂)

对于求幂，往往很多人认为是非常耗时的算法，其实只要用了以下的快速幂到方法，就可以把朴素的（O(N))的效率提高到(O(log2(N))

朴素的算法很简单，但是复杂度很高，大致如下

while(pow--)

ret*=base;

很容易想到，其实比如说算2^4的时候当算到2^2时只要平方一下就好了不用再算2^3的值是多少。下面的快速幂的方法就要用到这一点，利用二进制的方法减小复杂度。

用临时变量tmp记录现在算到的幂（即上文说到2^2)大体思路是这样的，我们只在二进制位为1的位做一次，返回值变量(ret)乘以tmp。为了方便测试我在下面的代码里到返回值都对一个10^7的质数区余。

大致代码如下：

#include

#define M 1000000007

int fp(int a,int b){

long long ret=1,pow=a;//ret：返回值；pow：基底

while(b!=0){

if(b&1) ret=(ret*pow)%M;

pow=(pow*pow)%M;

b/=2;//相当于b>>1

}

return (int)ret;

}

int main(){

int a,b;

scanf("%d%d",&a,&b);

printf("%d\n",fp(a,b));

}

随便做了一组测试即2^10000000000只用了4ms,绝对迅速！