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,绝对迅速！
