Python实现非齐次线性丢番图方程的表达式化简求助

问题描述 #

输入非齐次线性丢番图方程如 7x+13y = 1，现有代码返回嵌套形式的表达式：

1=7-(1*(13-(1*7))

需要将右侧化简为仅以输入系数（7和13）表示的线性组合形式，最终得到：

1=(2*7)+(-1*13)

以便提取系数2和-1，进而推导x、y的整数解集。尝试使用SymPy的simplify方法时，要么返回原表达式要么报错，无法完成需求。

解决方案 #

方法1：扩展欧几里得算法直接计算系数 #

扩展欧几里得算法本身的核心就是求解 ax + by = gcd(a,b) 的整数解(x,y)，无需事后化简嵌套表达式，直接在算法过程中跟踪系数即可，这是最高效可靠的方式。

代码示例：

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

# 示例：求解7x +13y=1的一组特解
gcd, x_coeff, y_coeff = extended_gcd(7, 13)
# 格式化输出目标形式
print(f"{gcd}=({x_coeff}*7)+({y_coeff}*13)")
# 输出结果：1=(2*7)+(-1*13)

方法2：用SymPy展开嵌套表达式（适用于已有中间表达式的场景） #

如果已经得到了嵌套形式的表达式字符串，需要先补全语法缺失的括号（原输出少一个右括号），再用SymPy解析并展开合并同类项：

代码示例：

from sympy import parse_expr, expand

# 补全括号后的嵌套表达式字符串
expr_str = "7-(1*(13-(1*7)))"
# 解析为符号表达式并展开
simplified_expr = expand(parse_expr(expr_str))
# 格式化为目标输出形式
term1_coeff = simplified_expr.as_ordered_terms()[0].as_coeff_mul()[0]
term2_coeff = simplified_expr.as_ordered_terms()[1].as_coeff_mul()[0]
print(f"1=({term1_coeff}*7)+({term2_coeff}*13)")
# 输出结果：1=(2*7)+(-1*13)

# 提取系数
terms = simplified_expr.as_ordered_terms()
coeffs = {}
for term in terms:
    coeff, factors = term.as_coeff_mul()
    var = factors[0] if factors else 1
    coeffs[var] = coeff
print(f"系数：x={coeffs[7]}, y={coeffs[13]}")
# 输出结果：系数：x=2, y=-1

关键注意点 #

1. 原输出的嵌套表达式存在语法错误（缺少一个右括号），这是导致SymPy解析报错的主要原因，必须先补全括号。
2. 优先使用扩展欧几里得算法直接计算系数，避免事后化简的额外步骤和潜在问题。

内容的提问来源于stack exchange，提问作者user1254621