快速幂

快速幂

快速幂, 二进制取幂(Binary Exponentiation, 也称平方法), 是一个在 $O(\log{n})$ 的时间内快速计算 $a^n$ 的小技巧, 而暴力的计算需要 $O(n)$ 的时间

推荐学习链接:

• OI-WIKI https://oi-wiki.org/math/binary-exponentiation/
• 知乎博主pecco https://zhuanlan.zhihu.com/p/95902286

1. 算法描述

首先, 思考一个问题: 如何快速地2计算出 7的10次方?

• 方法1: 暴力一点, $77=49$, $497 =343$, …, 需要进行 $9$ 次乘法
• 方法2: 先计算 $7^5$, 然后计算 $(7^5)^5$, 需要进行 $4+1=5$ 次乘法
• 方法3: 先计算 $77$, 然后计算$7^5=7^27^2*7$, 然后计算$7^10$, 需要进行 $4$ 次乘法

2. 递归快速幂

我们发现, 我们可以通过将 $7^10$ 拆成更小的任务来加快计算速度, 这样就可以自然地得到一个 递归 思路:

\[a^n= \begin{cases} a^{n - 1}*a, &if\ n\ is\ odd\\ a^{\frac{n}{2}}*a^{\frac{n}{2}}, &if\ n\ is\ even\ but\ not\ 0\\ 1, &if\ n = 0 \end{cases}\]

// 递归快速幂
int qpow(int a, int n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else
    {
        int temp = qpow(a, n / 2);
        return temp * temp;
    }
}

注意: 这里的 temp 变量是必要的, 因为如果写成 return qpow(a, n/2)*qpow(a, n/2) 就会计算两次 qpow(a, n/2)

3. 非递归快速幂

递归虽然简洁2, 但会产生额外的空间开销, 可以将递归写成循环, 也就是 非递归快速幂

这里我们引入 二进制取幂: 将指数 $n$ 按照 二进制表示 分割成更小的任务

举个栗子:

\[3^{13}=3^{(1101)_2}=3^8 * 3^4 * 3^1\]

由于 $n$ 有 $\lfloor \log_{2}{n} \rfloor + 1$ 个二进制位, 因此只要预先知道 $a^1, a^2, a^4, a^8, …, a^{2^{\log_{2}{n}}}$, 就可以只计算 $O(\log{n})$ 次乘法就可以计算出 $a^n$

那么, 如何快速地处理出 $a^1, a^2, a^4, a^8, …, a^{2^{\log_{2}{n}}}$?

我们可以发现:

\[\begin{equation}\begin{split} &3^1=3\\ &3^2=(3^1)^2\\ &3^4=(3^2)^2\\ &3^8=(3^4)^2\\ \end{split} \end{equation}\]

因此, 我们只需要不断地把 底数平方 即可

// 非递归快速幂
int qpow(int a, int n){
    int ans = 1;
    while(n) {
        if (n & 1)
            ans *= a;
        a *= a;
        n >>= 1;
    }
    return ans;
}

4. 模意义下取幂

在实际问题中, 因为计算结果可能会非常大, 题目常常会要求对一个大素数取模, 此时我们只需要 步步取模, 特殊情况(如mod较大), 还需要开 long long

// 模意义下取幂
int qpow(int a, int n){
    int ans = 1;
    while(n) {
        if (n & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans % mod;
}

5. 快速幂拓展

// 泛型的非递归快速幂
template <typename T>
T qpow(T a, ll n)
{
    T ans = 1;  // 赋值为乘法单位元, 可能要根据构造函数修改
    while (n)
    {
        if (n & 1)
            ans = ans * a;  // 这里就最好别用自乘了, 不然重载完 `*` 还要重载 `*=`, 有点麻烦
        n >>= 1;
        a = a * a;
    }
    return ans;
}