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

Question

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

或更一般的:是否存在零或正整数n1,n2,n3... 可以求解方程k1n1+k2n2+k3n3... =m 其中 k1,k2,k3... 和 m 是已知的正整数。

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

编辑:

关于该算法的实际使用:

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

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——一般来说，n+6k 对所有 k >= 0。另一方面一方面，如果你无法获得某个数字 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's algorithm 使用 0 作为初始节点.算法找到的距离将正是我们正在搜索的那些数字。

在我们的例子中 (6,7,15) 数字 7 产生 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 不可用(好吧，我们之前手动检查过)。

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

Polish Olympiad上出现了这个问题，允许多个查询，我翻译了解决方案。现在，如果您现在听到有人说计算机科学对真正的程序员没有用，请打他的脸。