# 快速冪 exponentiating by squaring
###### tags: `Algorithm`
> [https://meteor.today/article/PL8R-c](https://meteor.today/article/PL8R-c)

若n是2的整數次方 要算a^n是多少 只要算a^(n/2) 再平方就好了.
那麼 求出a^n的時間複雜度就是O(log(n)) 那如果n不是2的整數次方 該怎麼辦？
只要用上面算的過程中 得到的那幾個數字去湊就好了！
例如 a^13=(a^8)*(a^4)*(a^1) 用上面的方法 a^8、a^4、a^1在O(log(n))的時間複雜度就可以得到 而乘起來的過程 最多也不會乘超過log(n)次 所以複雜度是O(log(n)) 快速冪就這麼完成了！

5=101
ex 3^5
=3^(2^2*1)*3^(2^1*0)*3(2^0*1)

int pow( int x, int n){
    int ans = 1;
    while( n>0){ if(n&1)ans*=x; x*=x, n>>=1; }
    return ans;
}