快速幂

暴力求幂是$O(n)$的，快速幂相当于是二分进行计算。

• 递归版：

    long long binpow(long long a, long long b) {
      if (b == 0) return 1;
      long long res = binpow(a, b / 2);
      if (b % 2)
        return res * res * a;
      else
        return res * res;
    }

• 迭代版：将b的二进制位为1的位对应的幂相乘。某位对应的幂就是前一位对应的幂的平方。

    long long binpow(long long a, long long b) {
      long long res = 1;
      while (b > 0) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
      }
      return res;
    }