扩展欧几里得 Extended GCD

求解 ax + by = gcd(a,b) 的整数解。观察递归回溯过程中每层 x/y 系数的推导与贝祖等式验证。

速度:

a:b:

黄色=当前递归层，绿色=已求解出系数，蓝色=递归基

求 240·x + 46·y = gcd(240, 46)

深度 0exgcd(240, 46)q = ⌊240/46⌋ = 5x=? y=?

调用 exgcd(240, 46)，b=46 ≠ 0，递归计算 exgcd(46, 240 % 46 = 10)

步骤 1 / 22调用 exgcd(240,46)

当前高亮行: 2(调用 exgcd(240,46))

1function exgcd(a, b) {

2 if (b === 0) return { g: a, x: 1, y: 0 };

3 const { g, x: x1, y: y1 } = exgcd(b, a % b);

4 const x = y1;

5 const y = x1 - Math.floor(a / b) * y1;

6 return { g, x, y };

加载中…