时间戳

首页 > 解决方案 > 线性丢番图方程，扩展欧几里得算法

math - 线性丢番图方程，扩展欧几里得算法

问题描述

假设我想找到x 和 y 的任何值，使它们满足x . W + y . D = P

这可以通过以下使用扩展欧几里得算法来完成

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
       x = 1;
       y = 0;
       return a;
    }
    int g, xi, yi;
    g = exgcd(b, a % b, xi, yi);
    x = yi;
    y = xi - (a / b * yi);
    return g;
}

但这只是一些满足方程的随机 x 和 y

假设我添加了一个额外的约束，我想要任何 xyz 这样

x>=0 y>=0 z>=0 and x + y + z = n

我怎样才能有效地（如果可能，请分享代码/伪代码）找到所有这样的 xy 和 z？

我的问题归结为找到任何 x 和 y（使用扩展欧几里得算法）

1) 满足一个线性方程

2) 落在给定范围内

如果您愿意，这里是问题的链接

标签： mathdiophantine

解决方案

好的，所以我们有 2 个方程和 3 个未知数，所以做一些简单的数学运算，我们可以找到我们需要求解的方程

x * W + y * D + z * 0 = p

和

x + y + z = n

给定

x,y,z >=0

所以首先我们将通过循环任何一个未知数来减少一个未知数让我们说z

我们对 z 进行 0 - n 迭代，我们的新方程将是

x * w + y * d = p

和

x + y = m   { m is n - z for value of z in current iteration

现在我们有 2 个方程和 2 个未知数

所以我们现在可以通过在第一个方程中代入 x 来简化 x 和 y 的解

这使得它

(m - y) * w + y * d = p

这可以简化为

y = (p - m * w) / (d - w)

和

x = m - y

您可以在 x 和 y 是整数的第一个值处停止

推荐阅读