方程"a + bx = c + dy"的积分解

Question

在等式中a + bx = c + dy,所有变量都是整数.a,b,c,和d是已知的.我如何找到x和y？的整体解决方案？如果我想正确的,就会有解决方案无限多的,通过的最小公倍数分开b和d,但我需要的是一个解决方案,我可以计算出的其余部分.这是一个例子:

a = 2
b = 3
c = 4
d = 5
a + bx: (2, 5,  8, 11, 14)
c + dy: (4, 9, 14, 19, 24)

a + bx intersects c + dy at 14, so:
x = 4
y = 2

现在,我循环遍历整数值,x直到找到y(伪代码)的整数值:

function integral_solution(int a, int b, int c, int d) {
    // a + bx == c + dy
    // (a + bx - c) / d == y

    // Some parameters may have no integral solution,
    // for example if b == d and (a - c) % b != 0
    // If we don't have a solution before x == d, there is none.

    int x = 0;
    while (x < d)
    {
        if ((a + bx - c) % d == 0)
        {
            return [x, (a + bx - c) / d];
        }
        x++;
    }
    return false;
}

我觉得有更好的方法来做到这一点.有没有办法找到没有循环的x和y？我正在使用C++,如果这是重要的话.

Answer 1

线性丢番图方程采用的形式ax + by = c.如果c是的最大公约数a和b这意味着a=z'c和b=z''c那么这是贝祖等式形式的

用a=z'和b=z'',方程有无穷多的解.因此,而不是试用搜索方法可以检查是否c是最大公约数(GCD)的a和b(在你的情况下,这转化为bx - dy = c - a)

如果确实是a并且b是c当时的倍数x并且y可以使用扩展的欧几里德算法来计算,该算法找到整数x并且y(其中一个通常是负的)满足Bézout的身份

你的答案是:

a = k*x, b = k*y, c - a = k * gcd(a,b)对于任何整数ķ.

(作为旁注:这也适用于任何其他欧几里德域,即多项式环和每个欧几里德域都是唯一的分解域).您可以使用迭代方法来查找这些解决方案:

迭代方法

通过扩展和分组类似术语的常规代数(参考前面提到的维基百科文章的最后一节),获得了以下迭代方法:

• 1.应用欧几里德算法,让qn(n从1开始)成为除法中的有限商数列表.
• 2.将x0,x1初始化为1,0和y0,y1分别为0,1.
  • 2.1然后对于每一个i,只要定义了qi,
  • 2.2计算xi + 1 = xi-1 - qixi
  • 2.3计算yi + 1 = yi-1 - qiyi
  • 2.4将i递增1后重复上述步骤.
• 3.答案是xn和yn的倒数第二.

伪代码:

function extended_gcd(a, b)
    x := 0    lastx := 1
    y := 1    lasty := 0
    while b ? 0
        quotient := a div b
        (a, b) := (b, a mod b)
        (x, lastx) := (lastx - quotient*x, x)
        (y, lasty) := (lasty - quotient*y, y)       
    return (lastx, lasty)

其计算所以我写了例如算法最大公约数用欧几里德算法迭代法对非负a和b(负- 这些都需要额外的步骤),它返回GCD和存储解决方案x,并y通过引用传递给它的变量:

int gcd_iterative(int a, int b, int& x, int& y) {
    int c;
    std::vector<int> r, q, x_coeff, y_coeff;
    x_coeff.push_back(1); y_coeff.push_back(0);
    x_coeff.push_back(0); y_coeff.push_back(1);

    if ( b == 0 ) return a;
    while ( b != 0 ) {
            c = b;
            q.push_back(a/b);
            r.push_back(b = a % b);
            a = c;
            x_coeff.push_back( *(x_coeff.end()-2) -(q.back())*x_coeff.back());
            y_coeff.push_back( *(y_coeff.end()-2) -(q.back())*y_coeff.back());
    }
    if(r.size()==1) {
        x = x_coeff.back();
        y = y_coeff.back();
    } else {
        x = *(x_coeff.end()-2);
        y = *(y_coeff.end()-2);
    }
    std::vector<int>::iterator it;
    std::cout << "r: ";
    for(it = r.begin(); it != r.end(); it++) { std::cout << *it << "," ; }
    std::cout << "\nq: ";
    for(it = q.begin(); it != q.end(); it++) { std::cout << *it << "," ; }
    std::cout << "\nx: ";
    for(it = x_coeff.begin(); it != x_coeff.end(); it++){ std::cout << *it<<",";}
    std::cout << "\ny: ";
    for(it = y_coeff.begin(); it != y_coeff.end(); it++){ std::cout << *it<<",";}
    return a;
} 

从维基百科传递给它一个例子a = 120,b = 23我们得到:

int main(int argc, char** argv) {   
    // 120x + 23y = gcd(120,23)
    int x_solution, y_solution;
    int greatestCommonDivisor =  gcd_iterative(120, 23, x_solution, y_solution);
    return 0;
}

r:5,3,2,1,0,

q:5,4,1,1,2,

x:1,0,1,-4,5,-9,23,

y:0,1,-5,21,-26,47,-120,

什么是符合此示例的给定表: