快速幂

引入

1、假设我们要计算 $a^n$ 的值，最朴素的做法是循环 $n$ 次，每次在结果上乘以 $a$。显然这种做法的时间复杂度为 $O(n)$，但当 $n$ 非常大时这种做法的效率仍然较低，而快速幂可以解决这个问题
2、我们先从一个特例引入：当 $n$ 是 $2$ 的幂时，例如求 $a^{64}$ 的值，我们可以按照下表的方式计算。每次将上一次循环得到的结果自乘，就得到了指数为下一级 $2$ 的幂的结果，以此类推，便很快就能得到指数为所求 $2$ 的幂的结果
3、而对于任意的 $n$，例如求 $a^{105}$ 的值，我们可以将指数 $n$ 拆分成多个 $2$ 的幂之和，例如 $a^{105} = a^{1+8+32+64} = a^1 * a^8 * a^{32} * a^{64}$ ，而单独计算这些幂便十分简单了，因此最终只需要将需要的 $2$ 的幂的结果相乘即可
4、因此，快速幂又称二进制取幂(平方法)，其英文为Binary Exponentiation，其时间复杂度仅需 $O(log_2 n)$ 对数级

第 i 次循环计算的值第 i 次循环计算的值

1 a¹ * a¹ = a² 4 a⁸ * a⁸ = a¹⁶

2 a² * a² = a⁴ 5 a¹⁶ * a¹⁶ = a³²

3 a⁴ * a⁴ = a⁸ 6 a³² * a³² = a⁶⁴

第 i 次循环	计算的值	第 i 次循环	计算的值
1	a¹ * a¹ = a²	4	a⁸ * a⁸ = a¹⁶
2	a² * a² = a⁴	5	a¹⁶ * a¹⁶ = a³²
3	a⁴ * a⁴ = a⁸	6	a³² * a³² = a⁶⁴

代码实现

1、这个算法的关键，在于如何将 $n$ 分解为多个 $2$ 的幂之和。如上例，$105$ 的二进制为 $1101001$ ，我们发现其二进制 $1$ 的位置的权重便是拆开后所需的 $2$ 的幂(最右起第一个 $1$ 权重为 $2^0$ ，第二个 $1$ 权重为 $2^3$ ，第三个 $1$ 权重为 $2^5$ ，第四个 $1$ 权重为 $2^6$)
2、因此，我们可以通过这种方式完成拆分。代码实现模板如下，其中部分细节解释如下图(以计算 $7^{105}$ 为例)

// 快速幂，计算 a 的 n 次方
unsigned long long BinExp(int a, int n)
{
    unsigned long long result = 1;

    // 拆分指数 n，只要 n 不为 0 便继续循环
    while (n)
    {
        // 如果 n 的二进制最后一位是 1
        if (n & 1)
            // result 乘上 a 的 `2的当前位权值次方` 的结果
            result *= a;

        // a 自乘，a 变成下一级 a 的 `2的幂次方` 的结果，a^2 -> a^4 -> a^8
        a *= a;
        // 位运算右移一位，下一次循环判断下一位二进制
        n >>= 1;
    }

    return result;
}

幂取模

引入

1、计算 $a^n \bmod m$ 的值，其中 $a、n、m \in Z_+$，这种运算方式称为幂取模运算
2、注意：取模时，模乘运算是同样适用的，即 $(a * b) \bmod m = ((a \bmod m) * (b \bmod m)) \bmod m$
3、因此，我们只需要在快速幂的适当位置进行取模运算，就可以解决直接运算会超出范围的问题

代码实现

#include <iostream>
using namespace std;

// 幂取模
unsigned long long ModExp(int a, int n, int m)
{
    unsigned long long result = 1;
    a %= m; // 对第一次的乘数 a 取模

    while (n)
    {
        if (n & 1)
            result = (result * a) % m; // 对结果取模，结果又是下一次运算的乘数之一

        a = (a * a) % m; // 对乘数 a 取模
        n >>= 1;
    }

    return result;
}

int main()
{
    // 计算 a^n % m
    int a, n, m;
    cin >> a >> n >> m;

    unsigned long long ans = ModExp(a, n, m);
    cout << ans;
    return 0;
}

矩阵快速幂

引入

1、斐波那契数列：$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$ ，计算数列第 $n$ 项的值
2、将数列的第 $n+1$ 项和第 $n$ 项用列向量表示，其表示为 $(F_{n+1}, F_n)$ ，发现如下结论：
$$ \begin{aligned} \begin{pmatrix} F*{n+1} \\ F_n \\ \end{pmatrix} &= \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ \end{pmatrix} \cdot \begin{pmatrix} F_n \\ F*{n-1} \\ \end{pmatrix} \\ &= \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ \end{pmatrix} \cdot \begin{pmatrix} F*{n-1} \\ F*{n-2} \\ \end{pmatrix} \\ &= {\begin{pmatrix} 1 & 0 \\ 1 & 1 \\ \end{pmatrix}}^n \cdot \begin{pmatrix} F_1 \\ F_0 \\ \end{pmatrix} \\ \end{aligned} $$
3、因此，我们可以通过计算矩阵快速幂得到答案，其也只需要在快速幂上进行部分修改即可

代码实现

// 矩阵快速幂伪代码，只代表思路，不能直接运行
// 其中 A,result,I 都是矩阵
MAT MATExp(MAT A, int n)
{
    // 将 result 初始化为单位矩阵 I
    MAT result = I;

    while (n)
    {
        if (n & 1)
            result *= A;

        A *= A;
        n >>= 1;
    }

    return result;
}

快速幂

幂取模

矩阵快速幂

页底评论