快速幂

假设我们要计算 3¹³

若直接循环 13 次进行累乘，时间复杂度为 O(n)，在进行次数较高的处理时容易 TLE

这里引入倍增思想进行快速幂运算

实现

13 的二进制表示为 1101,即 8+4+2，我们很容易从里面看出倍增的要素

将 3¹³分解为 3⁸ · 3⁴ · 3¹进行计算，而后计算的数又可以依据前面计算过的数进行计算

n 有 logn+1 个二进制位，我们只需要计算 logn+1 次乘法即可

int quickpow(int a, int n) {
    int res = 1;
    while(n) {
        if(n & 1) // 该位二进制是否为 1
            res = res * a;
        a *= a; // 位数对应的基数
        n >>= 1; // n右移一位
    }
    return res;
}