1. 裴蜀定理：从基础到深入理解
作为一名算法竞赛选手，我最初接触裴蜀定理时就被它的简洁和强大所震撼。这个看似简单的定理，却在数论和算法设计中扮演着重要角色。让我们从基础开始，逐步深入理解这个定理。
1.1 裴蜀定理的表述与直观理解
裴蜀定理（Bézout's identity）的核心内容是：对于任意不全为零的整数a和b，存在整数x和y，使得ax + by = gcd(a,b)。换句话说，两个整数的线性组合能够表示它们的最大公约数。
这个定理的直观理解其实很简单。想象你手上有a和b两种面值的硬币，裴蜀定理告诉我们，通过适当组合这两种硬币，我们恰好能凑出它们的最大公约数金额。比如a=4，b=6，gcd(4,6)=2，确实有(-1)×4 + 1×6 = 2。
1.2 定理的严格证明
让我们更严谨地证明这个定理。证明分为两部分：必要性和充分性。
必要性证明：如果方程ax+by=c有整数解，那么gcd(a,b)必须能整除c。
设g=gcd(a,b)，那么g能整除a和b，因此也能整除ax+by的任何线性组合。所以g必须能整除c。
充分性证明：如果gcd(a,b)|c，那么方程ax+by=c有整数解。
这个证明更有趣，它实际上是构造性的。考虑所有形如ax+by的正整数集合，设其中最小的正数为d=ax₀+by₀。我们可以证明d就是gcd(a,b)：
- 任何a和b的公约数都能整除d，所以gcd(a,b)≤d
- 用带余除法证明d能整除a和b（类似欧几里得算法的证明）
- 因此d≤gcd(a,b)
- 综上d=gcd(a,b)
这个证明不仅说明了解的存在性，还暗示了如何找到解——这正是扩展欧几里得算法的基础。
1.3 定理的重要推论
从裴蜀定理可以得出几个重要推论：
- 互质判定：整数a和b互质（gcd=1）当且仅当存在整数x,y使ax+by=1
- 解的普遍形式：如果(x₀,y₀)是一个特解，那么所有解可以表示为：
x = x₀ + k×(b/g)
y = y₀ - k×(a/g)
其中g=gcd(a,b)，k为任意整数 - 解的扩展性：对于一般方程ax+by=c，当且仅当gcd(a,b)|c时有解
这些推论在实际应用中非常有用，特别是在解决线性丢番图方程和模逆元问题时。
2. 扩展欧几里得算法详解
理解了裴蜀定理后，我们需要一个实际计算x和y的方法，这就是扩展欧几里得算法（Extended Euclidean Algorithm）。
2.1 算法原理与实现
扩展欧几里得算法在计算gcd(a,b)的同时，还能找到满足ax+by=gcd(a,b)的整数x和y。它的核心思想是利用递归和数学归纳法。
算法实现如下（C++版本）：
cpp复制long long exgcd(long long a, long long b, long long &x, long long &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
long long d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
这个实现有几个关键点：
- 递归基：当b=0时，gcd(a,0)=a，此时x=1,y=0是显然解
- 递归调用：计算gcd(b, a%b)的同时交换x和y的位置
- 更新y值：y -= a/b * x
2.2 算法正确性证明
为什么这个算法能工作？让我们从数学上理解其正确性。
假设我们已经知道bx' + (a mod b)y' = gcd(b, a mod b) = gcd(a,b) = d的解(x',y')。因为a mod b = a - b⌊a/b⌋，所以：
bx' + (a - b⌊a/b⌋)y' = d
=> ay' + b(x' - ⌊a/b⌋y') = d
与我们要的ax + by = d比较，可以得到：
x = y'
y = x' - ⌊a/b⌋y'
这正是算法中交换x,y然后更新y的操作。这种递归关系保证了算法的正确性。
2.3 算法复杂度分析
扩展欧几里得算法的时间复杂度与标准欧几里得算法相同，都是O(log min(a,b))。这是因为每次递归调用都至少将问题规模减半。
空间复杂度也是O(log min(a,b))，因为递归深度与时间复杂度相同。在实际实现中，可以很容易地改为迭代版本以节省栈空间。
3. 扩展欧几里得算法的应用
掌握了扩展欧几里得算法后，我们来看看它的几个重要应用场景。
3.1 求解线性丢番图方程
给定方程ax + by = c，我们可以用扩展欧几里得算法来求解：
- 先用exgcd求出ax + by = gcd(a,b)的解(x₀,y₀)和d=gcd(a,b)
- 检查d是否整除c，如果不整除则无解
- 如果有解，特解为(x₀*(c/d), y₀*(c/d))
- 通解为：
x = x₀*(c/d) + k*(b/d)
y = y₀*(c/d) - k*(a/d)
其中k为任意整数
例如，解方程24x + 16y = 8：
- exgcd(24,16)得到x=-1,y=2,d=8
- 8|8，所以有解
- 特解：x=-1*(8/8)=-1, y=2*(8/8)=2
- 通解：x=-1+2k, y=2-3k (k∈ℤ)
3.2 计算模逆元
在模运算中，a关于模m的逆元是满足ax ≡ 1 (mod m)的整数x。根据定义，这等价于ax + my = 1。
因此，我们可以用扩展欧几里得算法来求逆元：
- 计算exgcd(a,m,x,y)
- 如果gcd(a,m)≠1，则逆元不存在
- 否则，x (mod m)就是a的逆元
例如，求7关于模19的逆元：
- exgcd(7,19,x,y)得到x=-8,y=3,d=1
- -8 mod 19 = 11
- 所以7的逆元是11，因为7×11=77≡1(mod19)
3.3 解线性同余方程
线性同余方程形如ax ≡ b (mod m)。解法如下：
- 转化为ax - my = b
- 用扩展欧几里得算法求解
- 如果有解，解的数量为gcd(a,m)个，间隔为m/gcd(a,m)
例如，解方程6x ≡ 2 (mod 8)：
- 转化为6x - 8y = 2
- exgcd(6,8)得到x=-1,y=1,d=2
- 2|2，有解
- 特解：x=-1*(2/2)=-1
- 通解：x=-1+4k (k∈ℤ)
- 在模8下，解为x=3和x=7
4. 实际编程中的注意事项
在实际编程实现和使用扩展欧几里得算法时，有几个关键点需要注意。
4.1 边界情况处理
- 零值处理：当a或b为零时，需要特殊处理。例如，gcd(a,0)=a，此时x=1,y=0
- 负数处理：算法应能正确处理负数输入。gcd(a,b)=gcd(|a|,|b|)，但解可能需要调整
- 溢出问题：当a和b很大时，中间计算可能溢出，需要使用更大整数类型
4.2 代码优化技巧
- 迭代实现：递归版本简洁但可能有栈溢出风险，可以改为迭代实现
- 减少计算：在更新y值时，可以用更高效的方式计算a/b
- 同时计算gcd：算法本身已经计算了gcd，可以避免重复计算
4.3 常见错误与调试
- 参数传递错误：确保x和y通过引用传递，否则结果不会更新
- 解的范围问题：得到的解可能很大或很小，需要根据应用场景调整
- 模运算处理：计算模逆元时，确保结果为正数
5. 算法竞赛中的应用实例
让我们看几个算法竞赛中扩展欧几里得算法的典型应用。
5.1 求解不定方程问题
问题：找到所有正整数解(x,y)满足3x + 5y = 100。
解法：
- 先用exgcd(3,5)找到特解：x₀=-100,y₀=100
- 通解：x=-100+5k, y=100-3k
- 要求x>0,y>0，解得20<k<33.33
- k取21到33，共13组解
5.2 组合数学问题
问题：计算有多少种方法用3元和5元硬币凑出100元。
这实际上就是求3x+5y=100的非负整数解的个数，解法同上，结果为13种。
5.3 模运算相关问题
问题：解同余方程7x ≡ 3 (mod 10)。
解法：
- 相当于解7x + 10y = 3
- exgcd(7,10)得到x=3,y=-2,d=1
- 特解x=3*3=9
- 唯一解x=9 (mod 10)
6. 扩展与变种
扩展欧几里得算法还有一些有趣的变种和扩展应用。
6.1 多元情况扩展
裴蜀定理可以推广到多个数的情况：对于a₁,...,aₙ，存在x₁,...,xₙ使得∑aᵢxᵢ=gcd(a₁,...,aₙ)。这可以通过迭代应用扩展欧几里得算法来实现。
6.2 多项式版本
在多项式环中也有类似的扩展欧几里得算法，用于求多项式的最大公因式和相应的线性组合。这在编码理论和密码学中有应用。
6.3 连分数与最佳逼近
扩展欧几里得算法与连分数有密切联系，可以用来找到实数的最佳有理逼近。这在数值计算和近似算法中有应用。
在实际编程练习中，我发现理解算法的数学本质比单纯记忆代码模板更重要。比如，为什么在递归调用时要交换x和y的位置？这个问题的答案直接来自于我们对算法正确性证明的理解。同样，处理边界情况的能力也依赖于对数学原理的深入把握。