快速幂

简介

快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 $O(log \ n)$ 的时间内计算 $a^{n}$ 的小技巧，而暴力的计算需要 $O(n)$ 的时间。而这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。其中显然的是它可以应用于模意义下取幂、矩阵幂等运算，我们接下来会讨论。

算法

计算 a 的 n 次方表示将 n 个 a 乘在一起： $a^{n} \ = a \ \times \ a \ \times \ \cdots \ \times \ a$ （n 个 a）

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

首先我们将 n 表示为 2 进制，举一个例子：

3^{(13)_{10}} \ = \ 3^{(1101)_{2}} \ = \ 3^{8} \ \cdot \ 3^{4} \ \cdot \ 3^{1}

因为 n 有 $\lfloor \log_{2}n \rfloor \ + \ 1$ 个二进制位，因此当我们知道了 $a^{1}, \ a^{2}, \ a^{4}, \ a^{8}, \ \cdots, \ a^{2^{\lfloor\log_{2}n\rfloor}}, \$ 后，我们只用计算 $O(\log n)$ 次乘法就可以计算出 $a^{n}$ 。

于是我们只需要知道一个快速的方法来计算上述 3 的 $2^{k}$ 次幂的序列。这个问题很简单，因为序列中（除第一个）任意一个元素就是其前一个元素的平方。举一个例子： \begin{matrix} 3^{1} & = & 3\ 3^{2} & = & (3^{1})^{2} & = & 3^{2} & = & 9\ 3^{4} & = & (3^{2})^{2} & = & 9^{2} & = & 81\ 3^{8} & = & (3^{4})^{2} & = & 81^{2} & = & 6561\ \end{matrix}

因此为了计算 $3^{13}$ ，我们只需要将对应二进制位为 1 的整系数幂乘起来就行了：

3^{13} \ = \ 6561 \ \cdot \ 81 \ \cdot \ 3\ = \ 1594323

将上述过程说得形式化一些，如果把 n 写作二进制为 $(n_{t}n_{t-1}\cdots n_{1}n_{0})$ ，那么有：

n \ = \ n_{t}2^{t} \ + \ n_{t-1}2^{t-1} \ + \ n_{t-2}2^{t-2} \ + \ \cdots \ + \ n_{1}2^{1} \ + \ n_{0}2^{0}

其中。那么就有

a^{n} \ = \ (a^{n_{t}2^{t} \ + \ \cdots \ + \ n_{0}2^{0}}) \ = \ a^{n_{0}2^{0}} \ \times \ a^{n_{1}2^{1}} \ \times \ \cdots \ \times \ a^{n_{t}2^{t}}

根据上式我们发现，原问题被我们转化成了形式相同的子问题的乘积，并且我们可以在常数时间内从 $2^{i}$ 项推出 $2^{i+1}$ 项。

这个算法的复杂度是 $O(\log n)$ 的，我们计算了 $O(\log n)$ 个 $2^{k}$ 次幂的数，然后花费 $O(\log n)$ 的时间选择二进制为 1 对应的幂来相乘。

模板

递归法

long long binpow(long long a, long long b)
{
    if (!b) 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;
}

应用

模意义下取幂

计算 $x^{n} \ mod \ m$

这是一个非常常见的应用，例如它可以用于计算模意义下的乘法逆元。

既然我们知道取模的运算不会干涉乘法运算，因此我们只需要在计算的过程中取模即可。

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

注意：根据费马小定理，如果 m 是一个质数，我们可以计算 $x^{n \ mod \ (m-1)}$ 来加速算法过程。

模意义下大整数乘法

计算 $a \ \times \ b \ mod \ m, \ a, \ b \ \leq \ m \ \leq \ 10^{18}$