快速 求幂（ 快速幂)

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

while(pow--)

   ret*=base;

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

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

4、大致代码如下：

#include<stdio.h>

#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));

}

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