当前位置：首页 > article >正文

【计算机科学】快速幂：指数运算的分治之美

article 2024/12/26 12:07:09

快速幂（Fast Power）是一种高效计算大数幂次模的算法，广泛应用于数论和算法竞赛中。与传统的暴力计算方法相比，快速幂通过将指数折半，显著降低了计算复杂度，使得原本需要线性时间的操作转变为对数时间，极大地提高了运算效率。本文将从基础入手，详细解析快速幂的原理与实现，探讨递归与迭代两种实现方式，并通过实例展示其在实际应用中的优势，帮助读者深入理解快速幂的核心思想与使用技巧。

题目描述

给你三个整数 $a, b, p$ ，求 $a^b \bmod p$ 。

结果输出一行一个字符串 a^b mod p=s，其中 $a, b, p$ 分别为题目给定的值， $s$ 为运算结果。

样例 #1

样例输入 #1

2 10 9

样例输出 #1

2^10 mod 9=7

样例解释

$2^{10} = 1024$ ， $\bmod 9 = 7$ 。

数据规模与约定

对于 $100\%$ 的数据，保证 $\leq a, b < 2^{31}$ ， $a + b > 0$ ， $\leq p < 2^{31}$ 。

思路分析

当我们需要计算较大数的幂时，直接进行指数次乘法显然是不可行的，因为它的时间复杂度为 $O (b)$ ，
即随着指数 $b$ 的增大，计算量成倍增长。在这个问题中，我们不仅需要计算大幂次，而且还需要对结果取模，
因此采用“快速幂”算法可以将时间复杂度降低到 $O(\log b)$ 。

快速幂的思想

快速幂是一种通过“折半”来减少计算次数的高效方法。普通计算幂次的方法需要进行指数次乘法，比如计算 $a^{10}$ 时需要乘 10 次，而快速幂则将计算次数减少到了指数的对数级别,即 $O(\log b)$ 。下面通过具体例子来说明这个过程。

举例理解

假设我们要计算 $2^{10}$ 。使用普通方法需要进行连续的乘法运算：

$\times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 ]$

这显然效率不高。快速幂通过以下步骤来优化计算：

指数拆分：首先将 10 转换为二进制形式： $10_{(10)} = 1010_{(2)}$ 。这意味着我们可以把 $2^{10}$ 表示为 $2^8 \times 2^2$ ，即 $2^{10} = 2^{(8+2)}$ 。
计算幂次的乘积：我们只需要计算 $2^8$ 和 $2^2$ ，然后将这两个结果相乘。这样，我们不需要每次都乘以 2，减少了计算的复杂性。
逐步计算：在快速幂中，我们通过不断将指数减半来计算。每次判断当前位的二进制是否为 1，如果是，就将当前的乘积乘到结果上。这样，指数每次被折半，直到变为 0。

思路总结

快速幂的关键在于将指数“折半”，通过利用二进制表示来减少乘法运算次数。使用这种方法，我们只需约 $O(\log b)$ 次运算，就能快速计算大指数的幂次。这种效率远高于普通的逐次乘法方法快。

快速幂的递归与迭代实现

我们可以使用递归与迭代两种方法实现快速幂算法。

递归：将问题分解为 $a^{b/2}$ 的幂次乘积。
迭代：每次对 $b$ 进行右移操作，从最低位逐位处理。

下面我们详细说明并比较两种实现。

快速幂的实现

方法一：递归实现

递归方法通过不断将指数对半拆分，从而实现指数乘法。实现代码如下：

#include "bits/stdc++.h"
using namespace std;

typedef long long LL;

LL pow_recursive(LL a, LL b, LL p) {
    if (p == 1) return 0; // 若模数为 1，直接返回 0
    if (b == 0) return 1; // 幂次为 0 时返回 1
    
    LL res = pow_recursive(a, b / 2, p);
    res = (res * res) % p;
    
    // 如果幂次是奇数，则多乘一次 a
    if (b % 2 != 0) res = (res * a) % p;
    
    return res;
}

解释：

当 $b$ 为 0 时，返回 1；
否则，递归计算 $a^{b/2} \mod p$ ，对其平方，若 $b$ 是奇数再乘一次 $a$ 。

方法二：迭代实现（推荐）

迭代方法比递归更简洁，且无需函数调用，效率稍高。

#include "bits/stdc++.h"
using namespace std;

typedef long long LL;

LL pow_iterative(LL a, LL b, LL p) {
    LL res = 1;
    a %= p; // 防止 a 过大，每次都对 a 取模
    
    while (b > 0) {
        if (b & 1) res = res * a % p; // 如果 b 的最低位是 1，结果乘以 a
        b >>= 1; // b 右移一位，相当于 b // 2
        a = a * a % p; // 每次对 a 自乘并取模
    }
    return res;
}

解释：

b & 1 用于判断 $b$ 的最低位是否为 1（即判断 $b$ 的奇偶性），若为 1，则结果乘上 $a$ ；
b >>= 1 表示将 $b$ 右移一位，即将 $b$ 减半；
每次将 $a$ 自乘并取模，这样减少了多余计算。

与暴力算法的比较

暴力算法

暴力算法的思路非常直观，即通过循环乘法来计算 $a^b$ 。伪代码如下：

LL pow_brute(LL a, LL b, LL p) {
    LL res = 1;
    for (LL i = 0; i < b; i++) {
        res = (res * a) % p;
    }
    return res;
}

复杂度： $O (b)$ ，当 $b$ 较大时运算量非常大，难以处理大数幂次。

快速幂的优势

快速幂的时间复杂度为 $O(\log b)$ ，相比暴力方法效率显著提升，尤其在处理大数幂次计算时非常有用。

复杂度分析

快速幂算法的时间复杂度为 $O(\log b)$ ，其中每次迭代都将指数 $b$ 减半，
从而将时间复杂度从 $O (b)$ 降低到 $O(\log b)$ ，适用于指数较大的情况。

代码实现

完整代码示例

#include "bits/stdc++.h"
using namespace std;

typedef long long LL;

LL pow_iterative(LL a, LL b, LL p) {
    LL res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = (res * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return res;
}

int main() {
    LL a, b, p;
    cin >> a >> b >> p;
    printf("%lld^%lld mod %lld = %lld\n", a, b, p, pow_iterative(a, b, p));
    return 0;
}