ACM-快速幂

简单位运算快速幂

假设我们要求a^{b，那么其实b是可以拆成二进制的，该二进制数第i位的权为2}(i-1)，例如当b==11时，a^11=a(2⁰⁺²1+2^3)

int poww(int a,int b){
    int ans=1,base=a;
    while(b!){
        if(b&1) ans*=base;
        base*=base;
        b>>=1;
　 }
    return ans;
}

11的二进制是``1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1，因此，我们将a¹¹转化为算a^(2^0)*a^(2^1)*a^(2^3)

其中比较重要的一步:base*=base,即基底不断增加,如果二进制是1则*上基底否则不,ans为所有基底相乘

base*base==base^2
下一步再乘，就是base^2*base^2==base^4
然后同理  base^4 * base4 = base^8 
see?是不是做到了base-->base^2-->base^4-->base^8-->base^16-->base^32.......
指数正是 2^i ，
再看上面的例子，a¹¹ =  a^(2^0) * a^(2^1) * a^(2^3)，
这三项是不是完美解决了，，嗯，快速幂就是这样。

▲.由于指数函数是爆炸增长的函数，所以很有可能会爆掉int的范围，根据题意决定是用 long long啊还是unsigned int啊还是mod某个数啊自己看着办。

typedef long long ll;
ll mod_pow(ll base,ll n,ll mod){
    ll res=1;
    while(n>0){
        if( n & 1 )  res = res*base%mod;
        base = base*base%mod;
        n>>= 1;
    }
    return res;
}