一、算法概述

  • 快速幂 (Fast Exponentiation)：用于高效计算 a^b mod m，时间复杂度 O(log b)，是模运算中最基础也最常用的算法之一。
  • 扩展欧几里得算法 (Extended Euclidean Algorithm, ExGCD)：不仅求出最大公约数 gcd(a, b)，还求出一组裴蜀等式系数 (x, y) 使得 a*x + b*y = gcd(a, b)，广泛用于求解模逆元。

二、核心思想

快速幂

  • 二进制拆分指数：将指数 b 按二进制位拆分。
    • 例如 a¹³ = a⁸ * a⁴ * a¹（因为 13₁₀ = 1101₂）。
    • 迭代每位：低位→高位，base 每次都平方（base = base * base % mod），若当前位为 1 则 result = result * base % mod。

扩展欧几里得

  • 基于辗转相除法反推系数：
    • 普通欧几里得：gcd(a, b) = gcd(b, a % b)，递归到底 gcd(g, 0) = g。
    • ExGCD 在递归返回时，利用下层结果 x₁, y₁（满足 b*x₁ + (a%b)*y₁ = g），推导出本层系数 x, y。
    • 关键公式：x = y₁，y = x₁ - (a / b) * y₁。

三、算法步骤 / 伪代码

快速幂（迭代版）：
输入：a, b, mod
输出：a^b mod mod
1. result = 1, base = a % mod
2. while b > 0：
     if b & 1：result = result * base % mod
     base = base * base % mod
     b >>= 1
3. return result

扩展欧几里得：
输入：a, b
输出：(gcd, x, y) 满足 a*x + b*y = gcd(a, b)
1. if b == 0：return (a, 1, 0)
2. (g, x1, y1) = exgcd(b, a % b)
3. x = y1
   y = x1 - (a / b) * y1
4. return (g, x, y)

四、C++ 代码实现

#include <iostream>
#include <tuple>
using namespace std;
using ll = long long;

// ==================== 快速幂：递归版 ====================
ll fastPowRecursive(ll a, ll b, ll mod) {
    if (b == 0) return 1 % mod;
    ll half = fastPowRecursive(a, b / 2, mod);
    half = half * half % mod;
    if (b & 1) half = half * (a % mod) % mod;
    return half;
}

// ==================== 快速幂：迭代版 ====================
ll fastPowIterative(ll a, ll b, ll mod) {
    ll result = 1 % mod;
    ll base = a % mod;
    while (b > 0) {
        if (b & 1) {
            result = result * base % mod;
        }
        base = base * base % mod;
        b >>= 1;
    }
    return result;
}

// ==================== 扩展欧几里得算法（ExGCD） ====================
// 返回 (gcd(a,b), x, y)，满足 a*x + b*y = gcd(a,b)
tuple<ll, ll, ll> exgcd(ll a, ll b) {
    if (b == 0) {
        return {a, 1, 0};
    }
    auto [g, x1, y1] = exgcd(b, a % b);
    // 递推公式：x = y1, y = x1 - (a/b) * y1
    ll x = y1;
    ll y = x1 - (a / b) * y1;
    return {g, x, y};
}

// ==================== 扩展欧几里得：迭代版 ====================
tuple<ll, ll, ll> exgcdIterative(ll a, ll b) {
    ll x0 = 1, y0 = 0;
    ll x1 = 0, y1 = 1;
    ll origA = a, origB = b;

    while (b != 0) {
        ll q = a / b;
        ll r = a % b;

        // 更新 a, b
        a = b;
        b = r;

        // 更新系数
        ll tempX = x0 - q * x1;
        ll tempY = y0 - q * y1;
        x0 = x1; y0 = y1;
        x1 = tempX; y1 = tempY;
    }
    // 此时 a 为 gcd, x0, y0 为系数
    return {a, x0, y0};
}

// ==================== 求模逆元（乘法逆元） ====================
// 求 a 在模 m 意义下的逆元，即 a * x ≡ 1 (mod m)
// 返回逆元；若不存在则返回 -1
ll modInverse(ll a, ll m) {
    auto [g, x, y] = exgcd(a, m);
    if (g != 1) {
        // 逆元不存在（a 和 m 不互质）
        return -1;
    }
    // 将 x 调整到 [0, m) 范围内
    x = (x % m + m) % m;
    return x;
}

// ==================== 测试用例 ====================
int main() {
    cout << "========== 快速幂 ==========" << endl;
    // LeetCode 50: Pow(x, n)
    ll mod = 1000000007;

    cout << "2^10  mod " << mod << " (递归) = " << fastPowRecursive(2, 10, mod) << " (答案: 1024)" << endl;
    cout << "2^10  mod " << mod << " (迭代) = " << fastPowIterative(2, 10, mod) << " (答案: 1024)" << endl;
    cout << "3^5   mod " << mod << " (迭代) = " << fastPowIterative(3, 5, mod)  << " (答案: 243)" << endl;
    cout << "2^31  mod " << mod << " (迭代) = " << fastPowIterative(2, 31, mod) << endl;
    cout << endl;

    cout << "========== 扩展欧几里得 (ExGCD) ==========" << endl;
    // a*x + b*y = gcd(a, b)
    auto [g1, x1, y1] = exgcd(30, 18);
    cout << "exgcd(30, 18):" << endl;
    cout << "  gcd = " << g1 << " (答案: 6)" << endl;
    cout << "  x = " << x1 << ", y = " << y1 << endl;
    cout << "  验证: " << 30 << "*" << x1 << " + " << 18 << "*" << y1 << " = " << (30*x1 + 18*y1) << endl;
    cout << endl;

    auto [g2, x2, y2] = exgcd(35, 15);
    cout << "exgcd(35, 15):" << endl;
    cout << "  gcd = " << g2 << " (答案: 5)" << endl;
    cout << "  x = " << x2 << ", y = " << y2 << endl;
    cout << "  验证: " << 35 << "*" << x2 << " + " << 15 << "*" << y2 << " = " << (35*x2 + 15*y2) << endl;
    cout << endl;

    // 迭代版 ExGCD
    auto [g3, x3, y3] = exgcdIterative(30, 18);
    cout << "exgcdIterative(30, 18):" << endl;
    cout << "  gcd = " << g3 << endl;
    cout << "  x = " << x3 << ", y = " << y3 << endl;
    cout << "  验证: " << 30 << "*" << x3 << " + " << 18 << "*" << y3 << " = " << (30*x3 + 18*y3) << endl;
    cout << endl;

    cout << "========== 模逆元 ==========" << endl;
    // 求 3 在模 11 下的逆元: 3*4=12≡1 mod 11，所以逆元是 4
    cout << "3 在模 11 下的逆元 = " << modInverse(3, 11) << " (答案: 4)" << endl;
    // 求 7 在模 26 下的逆元: 7*15=105≡1 mod 26，逆元是 15
    cout << "7 在模 26 下的逆元 = " << modInverse(7, 26) << " (答案: 15)" << endl;
    // 不存在逆元的情况（gcd != 1）
    cout << "4 在模 6 下的逆元 = " << modInverse(4, 6) << " (不存在: -1)" << endl;
    cout << endl;

    // 验证逆元
    ll inv = modInverse(3, 11);
    cout << "验证: 3 * " << inv << " mod 11 = " << (3 * inv % 11) << " (应为 1)" << endl;

    return 0;
}

五、复杂度分析

算法 时间复杂度 空间复杂度 说明
快速幂（迭代/递归） O(log b) O(1) 迭代 / O(log b) 递归栈 指数 b 每次右移一位，共约 log₂(b) 次迭代。每次迭代做 1~2 次模乘。
扩展欧几里得 O(log min(a,b)) O(1) 迭代 / O(log min(a,b)) 递归栈 递归层数等于辗转相除法的步数，与斐波那契数列相关，步数不超过 5 * log₁₀(min(a,b))。

六、应用场景

  1. LeetCode 50 Pow(x, n)：高效计算 x 的 n 次方。
  2. 模逆元计算：在组合数取模（Lucas 定理）、RSA 加密、中国剩余定理中等场景广泛使用。
  3. 矩阵快速幂：用于求解斐波那契数列第 n 项、线性递推等。
  4. 求解线性同余方程：a*x ≡ b (mod m) 可通过 ExGCD 转化为求逆元。
  5. 中国剩余定理 (CRT)：合并同余方程组时需要 ExGCD 求逆元。
  6. 快速求组合数：预处理阶乘及阶乘逆元，O(1) 查询 C(n, m) mod p。
  7. Miller-Rabin 素性测试：快速幂是其核心组成部分。

七、经典例题

例题1：LeetCode 50. Pow(x, n)

题目描述：实现 pow(x, n)，即计算 x 的整数 n 次幂函数。-2³¹ <= n <= 2³¹ - 1，-100.0 < x < 100.0。

解法说明：使用快速幂思想（迭代版更安全，避免递归栈溢出）。n 可能为负数，先处理 n < 0 取倒数。上述 C++ 代码中 fastPowIterative 稍作适配即可（将 mod 去掉，或对浮点数直接使用 double 版快速幂）。

浮点数版快速幂（对应 LeetCode 50）：

double myPow(double x, int n) {
    double result = 1.0;
    long long N = n;  // 防止 n = -2^31 取相反数溢出
    if (N < 0) { x = 1.0 / x; N = -N; }
    while (N > 0) {
        if (N & 1) result *= x;
        x *= x;
        N >>= 1;
    }
    return result;
}

例题2：模逆元求解

题目描述：给定 a 和质数 p，求 a 在模 p 意义下的乘法逆元，即求 x 使得 a*x ≡ 1 (mod p)。

解法说明：由于 p 是质数，gcd(a, p) = 1，调用 exgcd(a, p) 得到系数 x，调整到 [0, p) 即可。上述 C++ 代码中 modInverse 函数已实现该功能。

说明：以上 C++ 代码完整可编译，使用 g++ -std=c++17 -O2 filename.cpp -o main 编译后直接运行即可看到所有测试用例的输出。

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 14ms
  4. Powered by Hydro v5.0.1 Community