python扩展欧几里得算法

扩展欧几里得算法是一种用于求解一元线性同余方程的算法，可以表示为ax ≡ b (mod n)。在Python中，我们可以用以下函数来实现扩展欧几里得算法：

def extended_gcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, d = extended_gcd(b, a % b)
        return y, x - (a // b) * y, d

def solve_linear_congruence(a, b, n):
    x, y, d = extended_gcd(a, n)
    if b % d == 0:
        x0 = (x * (b // d)) % n
        for i in range(d):
            print("x ≡", (x0 + i * (n // d)) % n, "(mod", n, ")")
    else:
        print("无解")

在这段代码中，我们首先定义了一个`extended_gcd`函数，用于计算扩展欧几里得算法的结果。然后我们定义了一个`solve_linear_congruence`函数，用于解一元线性同余方程。这个函数会调用`extended_gcd`函数来得到结果，并根据情况输出方程的解或者无解情况。

通过这段代码，我们可以方便地在Python中使用扩展欧几里得算法来解决一元线性同余方程，这对于一些加密算法和数论问题来说是非常有用的。