扩展欧几里得
进阶扩展欧几里得是求解线性同余方程的基础。
// 算法讲解
扩展欧几里得
演示扩展欧几里得算法求解 ax + by = gcd(a,b) 的过程。
待机
速度 中
待机 ⌨1int extGcd(int a, int b, int& x, int& y) {
2 if (b == 0) { x = 1; y = 0; return a; }
3 int x1, y1;
4 int g = extGcd(b, a % b, x1, y1);
5 x = y1;
6 y = x1 - (a / b) * y1;
7 return g;
8}
复杂度分析
时间 O(log min(a,b))
空间 O(log min(a,b))
最优 O(1)
最坏 O(log min(a,b))
算法讲解
扩展欧几里得在求 GCD 的同时，顺便求出一组整数解 (x, y) 使得 ax + by = gcd(a,b)。
递推关系：x = y1, y = x1 - (a/b) * y1。
应用：求模逆元、解线性同余方程、中国剩余定理。
时间复杂度 O(log min(a,b))，与普通欧几里得相同。