解决线性丢番图方程的算法是什么：ax + by = c [英] What's algorithm used to solve Linear Diophantine equation: ax + by = c

问题描述

我正在这里寻找整数解决方案。我知道从第一对解和gcd（a，b）| c派生出无穷多个解。但是，我们如何找到第一对解决方案？有没有解决此问题的算法？

I'm looking for integers solution here. I know it has infinitely many solution derived from the first pair solution and gcd(a,b)|c. However, how could we find the first pair of solution? Is there any algorithm to solve this problem?

谢谢，

Chan

Thanks,
Chan

推荐答案

请注意，并非总是有解决方案。实际上，只有 c 是 gcd（a，b）的倍数，才有解决方案。

Note that there isn't always a solution. In fact, there's only a solution if c is a multiple of gcd(a, b).

也就是说，您可以使用扩展的欧几里得算法。

That said, you can use the extended euclidean algorithm for this.

这里是一个实现它的C ++函数，假设 c = gcd（a，b）。我更喜欢使用递归算法：

Here's a C++ function that implements it, assuming c = gcd(a, b). I prefer to use the recursive algorithm:

function extended_gcd(a, b)
    if a mod b = 0
        return {0, 1}
    else
        {x, y} := extended_gcd(b, a mod b)
        return {y, x-(y*(a div b))}

int ExtendedGcd(int a, int b, int &x, int &y)
{
    if (a % b == 0)
    {
        x = 0;
        y = 1;
        return b;
    }

    int newx, newy;
    int ret = ExtendedGcd(b, a % b, newx, newy);

    x = newy;
    y = newx - newy * (a / b);
    return ret;
}

现在，如果您有 c = k * gcd（ a，b）和 k> 0 ，则等式变为：

Now if you have c = k*gcd(a, b) with k > 0, the equation becomes:

ax + by = k*gcd(a, b) (1)
(a / k)x + (b / k)y = gcd(a, b) (2)

所以只需找到（2）的解决方案，或者找到（1）的解决方案，然后将 x 和相乘y 乘 k 。

So just find your solution for (2), or alternatively find the solution for (1) and multiply x and y by k.

这篇关于解决线性丢番图方程的算法是什么：ax + by = c的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！