扩展欧几里得算法 (Extended GCD) 模板详解

1. 简介

扩展欧几里得算法(Extended GCD)是欧几里得算法的扩展版本，不仅可以计算两个数的最大公约数，还可以找到一组整数解(x,y)满足贝祖等式：ax + by = gcd(a,b)。这个算法在解决线性同余方程和求解模逆元等问题中有重要应用。

主要特点：

• 计算最大公约数(GCD)
• 求解贝祖等式的整数解
• 用于求解线性同余方程
• 可用于计算模逆元

2. 实现原理

2.1 基本概念

1. 贝祖等式：

   • 对任意整数a,b，存在整数x,y使得：ax + by = gcd(a,b)
   • 这样的x,y称为贝祖系数

2. 最大公约数：

   • gcd(a,b)是同时整除a和b的最大正整数
   • 可以通过辗转相除法求得

2.2 核心策略

1. 递归过程：

   • 基于欧几里得算法的递归
   • 在回溯过程中计算贝祖系数

2. 解的构造：

   • 从最简单情况开始回溯
   • 逐步构造完整解

3. 模板代码

1
2
3
4
5
6
7
8
9
10
11
12

int exgcd(int a, int b, int &x, int &y) {
    // 递归边界
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    // 递归求解
    int g = exgcd(b, a % b, y, x);
    // 回溯更新
    y -= a / b * x;
    return g;
}

4. 函数说明

4.1 参数说明

1

int exgcd(int a, int b, int &x, int &y)

• a, b: 输入的两个整数
• x, y: 用于存储贝祖系数的引用
• 返回值：a和b的最大公约数

4.2 返回值

• 函数返回gcd(a,b)
• 通过引用返回满足ax + by = gcd(a,b)的一组解(x,y)

5. 时间复杂度分析

• 时间复杂度：O(log min(a,b))

  • 与欧几里得算法相同
  • 递归深度与较小数的对数成正比

• 空间复杂度：O(log min(a,b))

  • 递归调用栈的深度

6. 应用场景

1. 求解线性同余方程
2. 计算模逆元
3. 中国剩余定理(CRT)
4. 扩展中国剩余定理
5. 二元线性丢番图方程

7. 使用示例

7.1 求解线性同余方程

1
2
3
4
5
6
7
8

// 求解 ax ≡ b (mod m)
int solve_congruence(int a, int b, int m) {
    int x, y;
    int g = exgcd(a, m, x, y);
    if (b % g != 0) return -1;  // 无解
    x = (1LL * x * (b / g) % m + m) % m;
    return x;
}

7.2 计算模逆元

1
2
3
4
5
6
7

// 计算 a 在模 m 下的乘法逆元
int mod_inverse(int a, int m) {
    int x, y;
    int g = exgcd(a, m, x, y);
    if (g != 1) return -1;  // 不存在逆元
    return (x % m + m) % m;
}

8. 注意事项

1. 确保输入的整数在合理范围内
2. 注意处理负数和零的情况
3. 在求解同余方程时需要检查解的存在性
4. 计算过程中可能需要处理溢出问题

9. 总结

扩展欧几里得算法是数论中的重要工具，它不仅可以求最大公约数，还能找到贝祖等式的解。这个算法在解决同余方程、求解模逆元等问题中有广泛应用。通过递归的方式，算法既保持了简洁性，又实现了高效的计算。