如何用扩展欧几里得算法求解不定方程ax+by=c

扩展欧几里得算法可以用来求解不定方程ax+by=c，其中a、b、c为已知整数。

1. 首先，使用欧几里得算法求解a和b的最大公约数gcd(a,b)，同时得到一对整数(u,v)，使得au+bv=gcd(a,b)。

2. 接下来，判断c是否是gcd(a,b)的倍数。如果c不是gcd(a,b)的倍数，那么该不定方程没有整数解。否则，继续下一步。

3. 令k=c/gcd(a,b)，得到整数解为(x0,y0)=(uk,vk)。

4. 不定方程的通解为(x,y)=(x0+b/gcd(a,b)*t, y0-a/gcd(a,b)*t)，其中t为任意整数。

将以上步骤整合为一个示例代码：

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

def solve_diophantine(a, b, c):
    gcd, u, v = extended_gcd(a, b)
    if c % gcd != 0:
        return None
    else:
        k = c // gcd
        x0, y0 = u * k, v * k
        return x0, y0

a = 10
b = 6
c = 14
solution = solve_diophantine(a, b, c)
if solution is None:
    print("No solution")
else:
    x0, y0 = solution
    print("x =", x0, ", y =", y0)

此示例代码中，a=10，b=6，c=14为示例输入。输出为x=7，y=-14，即不定方程10x+6y=14的一个整数解