求线性方程的所有正积分解

Question

我玩的一个游戏有一个谜语，它涉及到解以下等式：

x*411 + y*295 + z*161 = 3200

我不想认为我只是把它放进了sympy，到那时为止我还没有真正使用过：

^{pr2}$

嗯，这只给了我一个相依的解，但是我想要所有可能的解，我把变量限制在，例如（假设没有其他解）[{x: 4, y: 2, z:6}]或{}

当然，我现在可以手动替换嵌套循环中的两个变量，或者手动解决它（就像我在上面得到的解决方案一样），但是我想知道如何让sympy（或另一个库）来为我完成它。在

Answer 1

SymPy可以solve Diophantine equations，但没有生成正解的内置方法。使用Sage可以很容易地做到这一点：下面是四行代码，它生成方程的所有非负整数解。在

p = MixedIntegerLinearProgram()
w = p.new_variable(integer=True, nonnegative=True)
p.add_constraint(411*w[0] + 295*w[1] + 161*w[2] == 3200)
p.polyhedron().integral_points()

输出是((4, 2, 6),)

在幕后，integral_points很可能只运行一个多循环；尽管当这似乎不起作用时，它尝试使用Smith范式。在

我知道你想要正解，但是（a）很容易从答案中排除任何包含零的元组；（b）在求解之前也很容易用x-1替换x，等等；（c）坚持“非负”可以很容易地使用Mixed Integer Linear Programming module创建多面体 同上。在

根据文献记载，人们还可以直接从不等式系统（“Hrep”）中构建Polyhedron object。这将允许一个人显式地说x>；=1，等等，但我在这条路线上没有成功。在

与SymPy

SymPy的丢番图模块的输出是一个参数解，如

^{pr2}$

在你的例子中。这可以在一个循环中以非常有效的方式生成解决方案。难点在于找到参数t_0和t_1的边界。由于这只是一个示例，我查看了上面的最后一个表达式，并将限制35200/4816和35200/295直接插入下面的循环中。在

^{3}$

输出是[4, 2, 6]。在