将EGCD方程转换为Python

Question

试图将这个EGCD方程转换为python。

egcd(a, b) = (1, 0), if b = 0
= (t, s - q * t), otherwise, where
q = a / b (note: integer division)
r = a mod b
(s, t) = egcd(b, r)

我使用的测试是egcd（5,37），它应返回（15，-2）但返回（19.5，-5.135135135135135）

我的代码是：

def egcd(a, b):
    if b == 0:
        return (1, 0)
    else:
        q = a / b # Calculate q
        r = a % b # Calculate r
        (s,t) = egcd(b,r) # Calculate (s, t) by calling egcd(b, r)
        return (t,s-q*t) # Return (t, s-q*t)

Answer 1

Python 3中的a / b是“真正的除法”，即使两个操作数都是ints，结果也是非截断浮点除法。

要修复，要么改为使用//（这是地板划分）：

q = a // b

或use divmod执行除法和余数作为单个计算，替换这两行：

q = a / b
r = a % b

只是：

q, r = divmod(a, b)

Answer 2

为q = a / b改变q = a // b