algorithm - 编写一个程序检查线性方程是否有正整数解

Question

我正在尝试编写一种算法来确定线性方程(特别是 ax + by = c 的形式)对于给定的 a、b、c 是否具有正整数解。它需要高效，因为数字 a、b 和 c 可以在 0<=a,b,c<=10^16 范围内。我将如何解决这个问题？

由于这是一个丢番图方程，我尝试检查 a 和 b 的 GCD 是否除以 c，但这样我无法区分正解、负解或零解。

Algorithm to determine non-negative-values solution existance for linear diophantine equation

我在这里找到了解决方案，但我不太明白。也许有人可以为我简化它？由于这个非常笼统，我只对具有 2 个变量的方程式感兴趣。

Answer 1

存在整数解

Bezout's identity确实告诉你 gcd(a,b) a 和 b 的最大公约数:

i) gcd(a,b) is the smallest positive integer that can be written as ax + by, and
ii) every integer of the form ax + by is a multiple of gcd(a,b).

就这样吧。如果c可被 gcd(a,b) 整除，您有解决方案。

寻找正解

从任何一对解决方案中，我们都可以得到所有其他解决方案。因此我们可以看看它们是否可以是积极的。仍然从相同的身份，我们得到:

When one pair of Bézout coefficients (x0, y0) has been computed (e.g., using extended Euclidean algorithm), all pairs can be represented in the form

现在我们完成了。您所要做的就是:

1. 使用扩展的欧几里得算法，它会给你
   • gcd(a,b)和
   • 一对(x0,y0)这样 a * x0 + b * y0 = gcd(a,b)
2. 检查是否gcd(a,b)划分 c .
   • 如果不是，则不存在解决方案。
   • 如果是，乘以x0和 y0通过 c / gcd(a,b)得到方程的解。
3. 如果x0和 y0两者都有相同的标志，你就完成了。
   • 如果它们都是正的，则您有正解，
   • 如果它们都是负数，你就不会。
4. 如果x0和 y0有不同的符号，选择最小的(绝对值)k改变负整数的符号。
   • 也就是说，如果x0为负，则取k = floor(d * x0 / b) (四舍五入到无穷大)
     如果是 y0为负，取k = ceil(-d * y0 / a)
   • 计算 (x1,y1) = (x0 - k * b / d , y0 + k * a / d)
     • 如果x1和 y1都是正数，你刚刚找到了两个正整数解。
     • 如果翻转一个数的符号会翻转另一个数，则无法找到正解。

请注意，它与您链接的问题有关，但变量数量不同。这已解决，因为您只有两个变量。