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