What is 快速幂？How does it work?

Today I will give you a shallow introduction to the fast power algorithm.

$\small{本文最后含有 彩蛋 哟！}$(づ′▽`)づ

$$\huge快速幂$$

$$\color{grey}{快速幂的实现原理及实现}$$

• 快速幂的用途

  • 顾名思义，快速幂就是很快速的幂运算，与朴素的 O(N) 相比效率有了极大的提高。
  • 试想当你面对一个问题：当要计算 a的N次方(mod p) 的时候，你的第一反应是开 long long 再循环一点一点求。
    这就是幂运算的 O(N) 算法,于是快速幂相关的各种题应运而生。简单地说，快速幂就是一种复杂度为 O(log N) 的求幂运算的算法。

$$\text{O(N) → O(logN)}$$

• 快速幂的实现原理

  • 因为快速幂的时间复杂度是O(log N) 的，所以我们自然而然地想到了二进制及位运算。这是显然的，我们知道，一个整数可以被拆分成若干个$2^k$的和。
  • 类比一下，对于一个幂运算问题 a^b，我们可以把 b 二进制分解，成为若干个 2^k 的和，那么对应下来就是这些和的幂的乘积。

  ---

  举个例子：
  $$a^b 且 b=11$$
  把 b 二进制分解，得:
  $$b=11=2^0+2^1+2^3$$
  因此，我们将a¹¹转化为：
  $$\large{a^{11}=a^{2^0}a^{2^1}a^{2^3}}$$

• 所以，我们就有了这样的一个原理：

在求解时，如果b是奇数，则原式为：
$$\large{a^b=a·a^{b-1}}$$

同理，若b是偶数，则原式变成：
$$\large{a^b=a^{\frac{b}{2}}·a^{\frac{b}{2}}}$$

$$\Large{这是一种 倍增 的思想}$$
$$于是，原来算法在时间复杂度上被优化了，诞生的新算法就是“快速幂”$$
$$\text{O(N) → O(logN)}$$

$$\text{This is how the fast power algorithm is implemented.}$$

• 快速幂的代码实现

根据我们刚刚学习的快速幂的实现原理，我们很容易发现，这可以用递归来实现。代码如下：

int qpow(int a, int b) {
  if (!b)
    return 1;
  else if (b & 1)
    return a * qpow(a, b - 1);
  else {
    int t = qpow(a, b >> 1);
    return t * t;
  }
}

但是令人遗憾的是，递归的常数巨大无比。彡(-_-;)彡
$$\large{于是上面的代码并不是一个资深OIer会选择的东西}$$

$$那快速幂怎么写保证常数不大呢？迭代上场！$$

• 我们会发现，无论 b 为何值，它在快速幂迭代的过程中只会进行2种操作 “-1” 或 “/2”。但无论采用哪种操作，都必会有一个时刻：b = 1。换而言之，至少会有一个时刻，b为奇数。

• 那么我们考虑，我们可以在“b/2”的迭代中，先不使迭代的结果影响到答案，而是先把迭代的结果储存下来，等到b为奇数时统一加到答案里。

• 这样就省去了繁琐的递归和记录答案的过程，保证了常数小，而且维护了答案的正确性。

代码如下：

int qpow(int a, int b) {
  int ret = 1;
  while (b > 0) {
    if (b & 1)
      ret *= a;
    a *= a;
    b >>= 1;
  }
  return ret;
}

• 快速乘的原理及其代码实现

其实，就是把快速幂的乘法运算变成了加法运算。（对，令你失望了e）

模板也大同小异:

typedef long long ll
ll qmult(ll a, ll b) {
  ll ret = 0;
  while (b > 0) {
    if (b & 1)
      ret = (ret + a) % mod;
    a = (a + a) % mod;
    b >>= 1;
  }
  return ret;
}

说了这么多，你学会了吗？ (*≧∪≦)

老规矩！

举手之劳，就点个赞再走呗 ε==(づ′▽`)づ
求支持，跪谢！ (>^ω^<)喵~

彩蛋：快速幂，总有些不正常人函数名写的是“KissMe”。（注：“快速幂”谐音“KissMe”）

看热闹代表作：y总搞笑经典语录