扩展欧几里得

概念讲解

什么是扩展欧几里得？

求解 ax+by=gcd⁡(a,b)ax + by = \gcd(a, b) 的一组整数解 (x,y)(x, y)。

裴蜀定理

对于任意整数 a, b，存在整数 x, y 使得 ax+by=gcd⁡(a,b)ax + by = \gcd(a, b)。

实现

12345678910int extgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

应用

1. 求逆元

如果 gcd⁡(a,m)=1\gcd(a, m) = 1，则 ax + my = 1 的 x 就是 a 模 m 的逆元。

2. 解线性同余方程

ax≡b(modm)ax \equiv b \pmod{m}

3. 解二元一次不定方程

ax+by=cax + by = c

考点分析

初赛考查方式

  1. 程序阅读： 扩展欧几里得
  2. 编程题： 逆元求解

常见考点

  • 扩展欧几里得原理
  • 逆元求解
  • 不定方程

例题精讲

例题 1：求逆元

题目： 求 3 模 11 的逆元。

解答：

3x + 11y = 1，解得 x = 4，所以逆元是 4。

验证：3 × 4 = 12 ≡ 1 (mod 11)

练习题

  1. 扩展欧几里得的原理是什么？
查看答案

扩展欧几里得的原理：

基于辗转相除法，在求 gcd 的同时，维护等式 ax+by=gcd⁡(a,b)ax + by = \gcd(a, b) 的解。

递归过程：

  1. 当 b=0b = 0 时，x=1,y=0x = 1, y = 0
  2. 否则，递归求解 bx′+(a mod b)y′=gcd⁡(a,b)bx' + (a \bmod b)y' = \gcd(a, b)
  3. 通过变换得到 x=y′,y=x′−⌊a/b⌋⋅y′x = y', y = x' - \lfloor a/b \rfloor \cdot y'
  1. 逆元存在的条件是什么？
查看答案

逆元存在的条件：gcd⁡(a,m)=1\gcd(a, m) = 1（a 和 m 互质）

如果 gcd⁡(a,m)≠1\gcd(a, m) \ne 1，则 a 在模 m 意义下没有逆元。

  1. 如何解线性同余方程？
查看答案

解 ax≡b(modm)ax \equiv b \pmod{m}：

  1. 用扩展欧几里得求 ax+my=gcd⁡(a,m)ax + my = \gcd(a, m) 的解
  2. 如果 b mod gcd⁡(a,m)≠0b \bmod \gcd(a, m) \ne 0，无解
  3. 否则，x=x0⋅bgcd⁡(a,m) mod mx = x_0 \cdot \frac{b}{\gcd(a, m)} \bmod m

易错点

⚠️ 注意：

  1. 逆元存在条件：gcd(a, m) = 1
  2. 解可能有多个，要取模
  3. 注意负数的处理
  4. 扩展欧几里得是数论基础