确定线性丢番图方程非负值解存在性的算法

Question

我正在寻找一种方法来确定方程是否有解，例如： 3n1+4n2+5n3=456，其中n1,n2,n3为正整数。

或者更一般地说：是否存在零或正整数n1,n2,n3...可以解方程k1n1+k2n2+k3n3...=m< /em> 其中 k1,k2,k3... 和 m 是已知的正整数。

我不需要找到解决方案 - 只需确定解决方案是否存在。

编辑：

关于该算法的实际使用：

在通信库中，我想在处理消息之前根据其大小确定给定消息是否有效。 例如：我知道一条消息包含零个或多个 3 字节元素、零个或多个 4 字节元素以及零个或多个 5 字节元素。我收到一条 456 字节的消息，我想在进一步检查其内容之前确定其有效性。 当然，消息的标头包含每种类型的元素数量，但我想通过传递诸如 pair 这样的内容来在通信库级别进行首次检查。 >。

Answer 1

您询问正则表达式

(xxx|xxxx|xxxxx)*

是否匹配 xx...x，其中 x 出现了 456 次。

这是 O(n+a^2) 的解决方案，其中 a 是左侧数字中最小的（在本例中为 3）。

假设你的数字是 6、7、15。我将用 6x+7y+15z 形式表示的数字称为“可用”。您要检查给定的号码是否可用。

如果你能够得到一些数字 n，那么你肯定能够得到 n+6、n+12、n+18 - 一般来说，对于所有 k >= 0，n+6k。另一方面，如果你无法得到某个数字n，那么n-6肯定也无法得到（如果你能得到（n-6），那么（n-6）+6=n将可用），这意味着n-12 、n-18、n-6k 也没有。

假设您确定 15 可用，但 9 不可用。在我们的例子中，15=6*0+7*0+15*1，但无论如何都无法得到 9。因此，根据我们之前的推理，15+6k 对于所有 k >= 0 可用，而 9-6k 对于所有 k >= 0 则不可用。如果你有一些数字除以 6 得到 3 作为余数（3、9、15、21，...），你可以快速回答：数字 <= 9 不可用，数字 >= 15 可用。

对于除以 6 的所有可能余数（即 0,1,2,3,4,5），确定可用的最小数是多少就足够了。 （我刚刚已经证明余数 3 的这个数字是 15）。

操作方法：创建一个包含顶点 0,1,2,3,4,5 的图。对于给定的所有数字 k (7,15 - 我们忽略 6)，添加一条从 x 到 (x + k) mod 6 的边。赋予它权重 (x + k) div 6。使用 Dijkstra 算法 使用 0 作为初始节点。算法找到的距离将正是我们正在搜索的数字。

在我们的例子中 (6,7,15)，数字 7 产生 0 -> 0。 1（权重1），1→ 2（权重1），2→ 3（权重1），...，5→ 0（权重1）和数字15给出0->； 3（权重2），1→ 4（权重2），...，5→ 1（重量2）。从 0 到 3 的最短路径有一条边 - 其权重为 2。因此 6*2 + 3 = 15 是余数为 3 的最小数。 6*1 + 3 = 9 不可用（好吧，我们之前手动检查过）。

与正则表达式有什么联系？好吧，每个正则表达式都有一个等效的有限自动机，我构建了其中一个。

这个问题，允许多个查询，出现在 波兰奥林匹克竞赛，我翻译了解决方案。现在，如果你听到有人说计算机科学对真正的程序员没有用，那就打他的脸。

Answer 2

根据此，如果 {n1, n2, n3, . ..} 不是 m 的约数，那么你就没有解。此页面仅显示 {n1, n2} 的示例，但它可以扩展到更大的系统。新问题是编写一个算法来查找最大公因数，但这对于原始问题来说是微不足道的。

所以你的算法的一部分会找到 gcf({n1,n2,...}) 然后看看它是否是 m 的一个因子。如果不是，则不存在解决方案。这并不能完全表明存在解决方案，但它可以快速向您表明不存在解决方案，这仍然很有用。

Answer 3

看起来您正在谈论具有整数约束的不等式系统。现实情况是您正在解决这个系统：

k1n1+k2n2+k3n3...=m
n1 >= 0
n2 >= 0
n3 >= 0

以及 n1、n2、n3 是整数的附加约束。这是一个线性规划问题。不幸的是，使用 整数约束解决此类系统的一般情况是 NP 完全的。但是，有许多算法可以为您解决这个问题。

Answer 4

这与Frobenius coin问题有关，该问题对于n>3尚未解决。

Answer 5

暴力方法（伪代码）：

def a = 3
def b = 4
def c = 5
def x = 456

for n1 = a to int(x / a) + 1 step a
  for n2 =b to int(x / b) + 1 step b
    for n3 = c to int(x / c) + 1 step c
      if a * n1 + b * n2 + c * n3 = x then
        print n1, n2, n3

另请参见 http:// /mail.python.org/pipermail/python-list/2000-April/031714.html

编辑： 在通信库中，这没有任何意义，因为它需要立即工作。在OP的应用程序中，我可能会使用某种哈希，但他的方法听起来很有趣。

Answer 6

这是关于 2 号案例的一些内容。我还没有弄清楚如何缩放它：

给定 2 个相对素数 x 和 y，存在正整数 a 和 b，使得所有 c>= 的 ax+by=c (x-1)(y-1)

基本上，这是有效的，因为如果您假设 x，您可以用 (0, y, 2y, 3y , ..., (x-1)y)。现在，通过添加 x 的一些正倍数，您可以达到 [(x-1)(y-1),(x-1)y] 之间的所有整数，因为 (x-1)(y- 之间的所有整数1) 和 (x-1)y-1 之前已经表达过。

1. GCD(x,y)。如果 c 不是倍数，则返回 false。
2. 如果 GCD(x,y) > 1，将 x,y,c 除以 GCD
3. 如果 c > (x-1)(y-1), 返回 true
4. 否则暴力破解

对于暴力破解：

if int(c/y) >= c*y^(-1) mod x, return true, 
else return false

Answer 7

也许以下信息是无关紧要的，因为它不能处理一般情况，但是...

如果问题是确定给定的正整数 K 是否可以形成和 3*n1 + 4*n2 + 5*n3，对于非负整数n1,n2,n3，那么答案是“是”，对于K>=3。Rosen

的著名教科书离散数学及其应用， p。第六版的第 287 号，利用归纳法证明“只需 4 分和 5 分邮票即可形成 12 分或以上的每笔邮资”。

基本步骤是用3张4美分的邮票可以形成12美分的邮资。

归纳步骤认为，如果使用四美分邮票 P(k) 为真，则只需用五美分邮票替换四美分邮票即可表明 P(k+1) 为真。
如果不使用四美分邮票 P(k) 为真，那么，因为 k>=12，所以我们至少需要 3 个五美分邮票来形成总和，并且 3 个五美分邮票可以用 4 个四美分邮票代替邮票实现k+1。

要扩展该问题的上述解决方案，只需要考虑更多的情况。