快速幂计算

快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 \(\Theta(\log n)\) 的时间内计算 \(a^n\) 的小技巧，而暴力的计算需要 \(\Theta(n)\) 的时间。

计算 a 的 n 次方表示将 n 个 a 乘在一起： \(a^{n} = \underbrace{a \times a \cdots \times a}_{n\text{a}}\)。然而当 \(a,n\) 太大的时侯，这种方法就不太适用了。不过我们知道：\(a^{b+c} = a^b \cdot a^c,\,\,a^{2b} = a^b \cdot a^b = (a^b)^2\)。二进制取幂的想法是，我们将取幂的任务按照指数的 二进制表示 来分割成更小的任务。

快速幂的思想其实很简单，就是公式的转换

1. 当指数是偶数时，我们可以让指数除以2，底数乘以底数
2. 当指数是奇数时，我们可以将指数变为偶数

例子：计算 \(2^{10}\)

1. 指数是偶数,\(2^{10} = 4^5\)
2. 指数是奇数，\(4^{5} = 4 \times 4^{4}\)
3. 指数是偶数，\(4 \cdot 4^{4} = 4 \cdot 16^2 = 4 \cdot 256^1\)
4. 指数是奇数，\(4 \cdot 256^1 = 4 \cdot 256 \cdot 256^0\)，指数为\(0\)时停止，那么答案就是\(4 \cdot 256 = 1024\)

代码实现如下:

// 递归实现
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;
}

// 非递归实现
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;
}

参考:

• 快速幂
• 快速幂计算——被TLE支配的恐惧