快速幂复习笔记

虽然快速幂的思想比较简单, 而且之前也复习过一遍了, 但是刚才写代码的时候还是重新推了一遍才想起来怎么写, 所以这里写(水)一篇 blog 来增强理解.

简介

快速幂是用来快速求解 $a^b(\bmod \, p)$ 的一种算法.

分析

当 b 不是很大的时候, 显然我们可以暴力求解 $a^b(\bmod \, p)$, 这时复杂度是 $\mathcal{O}(b)$ , 可是当 b 的数量级很大的时候怎么办呢?

这个时候就需要用到快速幂算法了.

当 b 为偶数时, $a^b=a^{\frac{b}{2}}\cdot a^{\frac{b}{2}}$ , 当 b 为奇数时, $a^b=a^{\frac{b}{2}}\cdot a^{\frac{b}{2}}\cdot a$.

我们要是知道 $a^{\frac{b}{2}}$ 就可以很快求出 $a^b$ 了, 这时很容易想到递归求解 $a^\frac{b}{2}$ , 毕竟这种情况下递归计算 $a^b$ 的复杂度是 $\mathcal{O}(\log{b})$ 的.

递归的实现方法很简单, 这里不再赘述.

我们考虑非递归式的写法.

在递归式写法中, 每递归一次, a 的次数就会翻一倍, 一共递归了 $\lfloor\log{b}\rfloor$ 次, 因此我们在循环过程中每次 a *= a 和 b >>= 1 即可, 但是如果 b 为奇数时需要再乘以原始的 a, 而此时 a 的值已经变了怎么办?

我们从一些简单的例子入手.

考虑 $b=5$ 和 $b=7$ 的情况.

$$a^5=a^2\cdot a^2\cdot a=(a\cdot a)(a\cdot a)a$$

$$a^7=a^3\cdot a^3\cdot a=(a^2\cdot a)(a^2\cdot a)a$$

在 $b=5$ 的情况下, 我们需要在第一次循环时乘以 a , 此时 a 的值没有变, 之后我们再令 a 自乘.

在 $b=7$ 的情况下, 第一次循环时的情况与 $b=5$ 的相同, 没有影响, 第二次循环时, 对于先前分出来的 2 个 $a^3$ 我们都要乘一次 a , 也就是需要乘两次 a , 相当于乘以 $a^2$ , 正好是此时 a 变化一次后的值.

同理, 我们可以看出, 当 b 更大, 需要乘 a 的次数更多的时候, 假设当前是第 k 次循环, 那么我们已经将 $a^b$ 拆成了 $2^k$ 个 $a^{b>>k}$ (当然还要算上奇数情况下多乘的 a )的形式, 当进入第 k + 1 次循环时, 若 b 为奇数, 这 $2^k$ 个 $a^{b>>k}$ 都要乘一个 a , 相当于乘上了一个 $a^{2^k}$ , 而可以发现这正好是当前 a 经过 k 次自乘后的值, 因此我们只需每次判断 b 的奇偶性, 若为奇数, 就 ret *= a 即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12

typedef long long ll;

ll binpow(ll a, ll b, ll p) {
    a %= p;
    ll ret = 1;
    while (b > 0) {
        if (b & 1) ret = ret * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ret;
}