快速幂

求a^n的值

//最容易想到的求a^n的代码  
typedef long long LL;
LL powr(LL a,LL n){
    if(n==0)return 1;
    else{
        LL ans=1;
        for(int i=1;i<=n;i++)ans=ans*a;
        return ans;
    }
}  

快速幂

用上面的代码求a^n的时间复杂度为O(n)，其实这个时间复杂度一般情况下还可以，但是如果遇到很大的n，那么最后求出的数据的值很大，计算量会暴涨。
快速幂运用了结合律的思想而且使用了位运算极大的节省了时间，一般情况下，位运算是比其他的运算快很多的，因为其他运算在计算机中都是转换为位运算来计算的。直接使用位运算也可以为我们节省很多的时间。

下面我们来看下快速幂的原理：
a^8=a a a a a a 共计算了7次
a^8=(a a a a)(a a a a)=(a a a a)^2共计算了4次
同理，继续进行结合a^8=((a * a)^2)^2计算了3次
如此重复，之前需要7次的计算现在只需要3次，时间复杂度降为o(logn),这样算来，如果指数为1e10，大约只要算34次。很大程度的减少了次数。
下面是快速幂的代码:

typedef long long LL;
LL Qpow(LL a,LL n){
    if(n==0)return 1;
    LL ans=1;
    while(n){
        if(n&1){//n为奇数 
            ans=ans*a;    
        }
        a*=a;
        n>>=1;//右移位，等价于除2 
    }
    return ans; 
} 

快速幂取模

//快速幂取模  
/*
根据模运算的公式：(m*n)%c=(m%c)(n%c)%c
*/
typedef long long ll;
ll quick(ll a,ll b,ll  c){
    ll ans=1;
    a=a%c;
    while(b!=0){
        if(b&1)ans=(ans*a)%c;
        b>>=1;
        a=(a*a)%c;
    }
    return ans;
}