扩展欧几里得算法 | 一瓜算法小册

[Desgard]

https://www.desgard.com/algo/docs/part2/ch02/3-ext-euclidean/

扩展欧几里得算法

[ctx2002]

能不能将python -- ext_gcd函数改一下，这样程序可以和上面的数学公式对上号。改了后， 移值到其它编程语言也容易。原来的程序中的那个几个‘x’变量的关系不容易看出。

def ex_gcd(a, b): if b == 0: return 1, 0, a else: x1, y1, r = ex_gcd(b, a % b) x0, y0 = y1, (x1 - (a // b) * y1) return x0, y0, r

[ctx2002]

a0​y1​−b0​[x1​−y1​(a0​∣b0​)]=gcd(a1​,b1​) 中的“-b0[‘ 因该是”+b0[“

a0​y1​−b0​[x1​−y1​(a0​∣b0​)]=a0​x0​+b0​y0 ​中的”−b0​[x1“ 因该是”+b0[x1“

[Desgard]

@ctx2002 能不能将python -- ext_gcd函数改一下，这样程序可以和上面的数学公式对上号。改了后， 移值到其它编程语言也容易。原来的程序中的那个几个‘x’变量的关系不容易看出。

def ex_gcd(a, b): if b == 0: return 1, 0, a else: x1, y1, r = ex_gcd(b, a % b) x0, y0 = y1, (x1 - (a // b) * y1) return x0, y0, r

好建议，我修改一下

[glmios]

非常清楚，　只有一个地方：　a0y1 - b0(x1-y1(a0|b0) = gcd(a1,b1) , 这个地方写错了，　应该是： a0y1 + b0(x1-y1(a0|b0) = gcd(a1,b1)