2

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

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

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

我在这里找到了解决方案，但我不太明白。也许有人可以为我简化它？因为这个很一般，我只对有 2 个变量的方程感兴趣。

4

1 回答 1

10

整数解的存在

Bezout 的恒等式确实告诉你，gcd(a,b)在 a 和 b 的最大公约数下：

i)gcd(a,b)是可以写成 ax + by 的最小正整数，并且
ii) 形式为 ax + by 的每个整数都是 的倍数gcd(a,b)。

所以你去。如果c可被 整除gcd(a,b)，则有解。

寻找积极的解决方案

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

当一对 Bézout 系数 (x0, y0) 已经被计算（例如，使用扩展欧几里得算法）时，所有对都可以表示为 所有解决方案

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

  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都是正数，你就找到了两个正整数解。
      • 如果翻转一个数字的符号会翻转另一个数字，则无法找到正解。

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

于 2014-12-13T14:59:36.910 回答