就像Bezout的身份一样，但具有自然数和任意常数。可以解决吗？

Question

我是一个业余演奏，播放离散数学。这不是 功课问题，尽管我在家做。

我想用a，b和c求解ax + by = c。 给出以及要计算的x和y。我想找到所有x，y对 这将满足方程式。

这与bezout的整数身份具有类似的结构 在哪里有多个（无限？）溶液对。我想 相似性可能意味着扩展的欧几里得算法 可以在这里提供帮助。以下是EEA的两个实现 似乎有效；它们都从网络上的代码中进行了调整。

这些是否可以适应任务，或者可能有人可以 找到一个更有前途的大道？

typedef long int Int;

#ifdef RECURSIVE_EEA
Int // returns the GCD of a and b and finds x and y 
// such that ax + by == GCD(a,b), recursively
eea(Int a, Int b, Int &x, Int &y) {
    if (0==a) {
        x = 0;
        y = 1;
        return b;
    }
    Int x1; x1=0;
    Int y1; y1=0;
    Int gcd = eea(b%a, a, x1, y1);
    x = y1 - b/a*x1;
    y = x1;
    return gcd;
}
#endif

#ifdef ITERATIVE_EEA
Int // returns the GCD of a and b and finds x and y 
// such that ax + by == GCD(a,b), iteratively
eea(Int a, Int b, Int &x, Int &y) {
    x = 0;
    y = 1; 
    Int u; u=1;
    Int v; v=0;         // does this need initialising?
    Int q;              // quotient
    Int r;              // remainder
    Int m;
    Int n;
    while (0!=a) {      
        q = b/a;        // quotient
        r = b%a;        // remainder
        m = x - u*q;    // ??  what are the invariants?
        n = y - v*q;    // ??  When does this overflow?
        b = a;          // A candidate for the gcd - a's last nonzero value.
        a = r;          // a becomes the remainder - it shrinks each time.
                        // When a hits zero, the u and v that are written out
                        // are final values and the gcd is a's previous value.
        x = u;          // Here we have u and v shuffling values out
        y = v;          // via x and y. If a has gone to zero, they're final.
        u = m;          // ... and getting new values
        v = n;          // from m and n
    }
    return b;
}
#endif

Answer 1

如果我们稍微更改方程式：

ax + by = c
by = c - ax
y =  (c - ax)/b

那么我们可以循环x通过其范围内的所有数字（a*x＆lt; = c），并计算如果可行的天然y存在。 没有无限数量的解决方案限制为min（c/a，c/b）

int a=123,b=321,c=987654321;
int x,y,ax;
for (x=1,ax=a;ax<=c;x++,ax+=a)
    {
    y = (c-ax)/b;
    if (ax+(b*y)==c) here output x,y solution somewhere;
    }

因此， y也只需检查c-ax是否可以通过b进行除外：

int a=123,b=321,c=987654321;
int x,y,ax,cax,by;
for (x=1,ax=a,y=(c/b),by=b*y;ax<=c;x++,ax+=a)
    {
    cax=c-ax;
    while (by>cax){ by-=b; y--; if (!y) break; }
    if (by==cax) here output x,y solution somewhere;
    }

如您现在可以看到的那样：您现在可以看到x，y在相同的循环中以相反的方向迭代，并且在循环中不再存在划分或乘法，因此在这里的首先要快得多：

      method1         method2
 [  78.707 ms] |  [  21.277 ms] // time needed for computation
         75044 |          75044 // found solutions
-------------------------------
    75,3076776 |     75,3076776 // first few solutions in x,y order
   182,3076735 |    182,3076735
   289,3076694 |    289,3076694
   396,3076653 |    396,3076653
   503,3076612 |    503,3076612
   610,3076571 |    610,3076571
   717,3076530 |    717,3076530
   824,3076489 |    824,3076489
   931,3076448 |    931,3076448
  1038,3076407 |   1038,3076407
  1145,3076366 |   1145,3076366

我希望，对于真正巨大的c和小a，b数字，这

while (by>cax){ by-=b; y--; if (!y) break; }

可能比使用GCD的实际除法速度慢。