Skip to content

快速幂

虽然快速幂的思想比较简单, 而且之前也复习过一遍了, 但是刚才写代码的时候还是重新推了一遍才想起来怎么写, 所以这里写(水)一篇 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 即可.

代码

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;
}

Comments