扩展欧几里得算法二元一次方程python

扩展欧几里得算法是求解形如ax+by=gcd(a,b)的不定方程的一种方法。其中a、b为整数，x、y为未知整数，gcd(a,b)表示a和b的最大公约数。在二元一次方程中，a和b的系数分别为A、B，未知数为x、y，则方程可以表示为Ax+By=C，其中C为常数。我们可以将其转化为ax+by=gcd(a,b)的形式，其中a=A/gcd(A,B)，b=B/gcd(A,B)，gcd(a,b)=1。然后使用扩展欧几里得算法求解x、y的值，最终得到Ax+By=C的解。下面是Python代码实现：
def exgcd(a, b):
if b == 0:
return 1, 0, a
else:
x, y, q = exgcd(b, a % b)
x, y = y, x - (a // b) * y
return x, y, q

def solve_equation(A, B, C):
gcd_AB = exgcd(A, B)[2]
if C % gcd_AB != 0:
return "No solution"
else:
x0, y0 = exgcd(A, B)[:2]
k = C // gcd_AB
return x0 * k, y0 * k
登录后复制
其中，exgcd函数是扩展欧几里得算法的实现，solve_equation函数是解二元一次方程的实现。如果方程有解，则返回x、y的值；否则返回"No solution"。