快速幂

快速幂
用于快速求a^b的算法
思想:拆分
例:求2^13
等价于求 2^1 2^4 2^8
其中13二进制表示(1101).对应十进制的位权为8，4，1.
因此对于求幂，我们可以将指数的二进制表示数每位所对应的十进制的位权作为拆分后的指数.
复杂度不难看出是O(logn).

#include <iostream>

int main () {
    int a, b;
    std::cin >> a >> b;
    long long ans = 1;
    while(b) {
        if(b & 1) {
            ans *= a;
        }
        a *= a;
        b >>= 1;
    }
    std::cout << ans;
    return 0;
}