快速幂

引入

1、假设我们要计算 aⁿ 的值，最朴素的做法是循环 n 次，每次在结果上乘以 a。显然这种做法的时间复杂度为 O(n)，但当n 非常大时这种做法的效率仍然较低，而快速幂可以解决这个问题
2、我们先从一个特例引入：当n 是 2 的幂时，例如求 a⁶⁴ 的值，我们可以按照下表的方式计算。每次将上一次循环得到的结果自乘，就得到了指数为下一级 2 的幂的结果，以此类推，便很快就能得到指数为所求 2 的幂的结果
3、而对于任意的 n，例如求 a¹⁰⁵ 的值，我们可以将指数 n 拆分成多个 2 的幂之和，例如 a¹⁰⁵ = a^{1 + 8 + 32 + 64} = a¹ * a⁸ * a³² * a⁶⁴，而单独计算这些幂便十分简单了，因此最终只需要将需要的 2 的幂的结果相乘即可
4、因此，快速幂又称二进制取幂(平方法)，其英文为Binary Exponentiation，其时间复杂度仅需 O(log 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⁰，第二个 1 权重为 2³，第三个 1 权重为 2⁵，第四个 1 权重为 2⁶)
2、因此，我们可以通过这种方式完成拆分。代码实现模板如下，其中部分细节解释如下图(以计算 7¹⁰⁵ 为例)

// 快速幂，计算 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ⁿ % m 的值，其中a、n、m 都是正整数，这种运算方式称为幂取模运算
2、注意：取模时，乘法运算是同样适用的，即(a * b) % m = ((a % m) * (b % m)) % 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, ...，计算数列第 n 项的值
2、将数列的第 n+1 项和第 n 项用列向量表示(如下图)，其表示为(F_n+1, F_n)，发现其等于矩阵 [[1, 1], [1, 0]] 乘以列向量 (F_n, F_n-1)，继续向下展开推导，最终发现其等于矩阵 [[1, 1], [1, 0]]ⁿ 乘以列向量 (F₁, F₀)
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;
}

快速幂

幂取模

矩阵快速幂

页底评论