快速 求幂（ 快速幂)

朴素的算法很简单，但是复杂度很高，大致如下while(pow--)   ret*=base;

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

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

大致代码如下：#include#define M 1int 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^1只用了4ms,绝对迅速！