algorithm - 求解线性方程

Question

我必须找出方程 ax+by=c 的积​​分解，满足 x>=0 和 y>=0 并且 (x+y) 的值是最小值。

我知道如果 c%gcd(a,b)}==0 那么它总是可能的。如何找到 x 和 y 的值？

我的方法

for(i 0 to 2*c):
    x=i
    y= (c-a*i)/b
    if(y is integer)
    ans = min(ans,x+y)

有没有更好的方法来做到这一点？具有更好的时间复杂度。

Answer 1

使用 Extended Euclidean Algorithm 和 linear Diophantine equations 的理论无需搜索。这是一个 Python 3 实现:

def egcd(a,b):
    s,t = 1,0 #coefficients to express current a in terms of original a,b
    x,y = 0,1 #coefficients to express current b in terms of original a,b
    q,r = divmod(a,b)
    while(r > 0):
        a,b = b,r
        old_x, old_y = x,y
        x,y = s - q*x, t - q*y
        s,t = old_x, old_y
        q,r = divmod(a,b)
    return b, x ,y

def smallestSolution(a,b,c):
    d,x,y = egcd(a,b)
    if c%d != 0:
        return "No integer solutions"
    else:
        u = a//d #integer division
        v = b//d
        w = c//d
        x = w*x
        y = w*y
        k1 = -x//v if -x % v == 0 else 1 + -x//v #k1 = ceiling(-x/v)
        x1 = x + k1*v # x + k1*v is solution with smallest x >= 0
        y1 = y - k1*u
        if y1 < 0:
            return "No nonnegative integer solutions"
        else:
            k2 = y//u #floor division 
            x2 = x + k2*v #y-k2*u is solution with smallest y >= 0
            y2 = y - k2*u
            if x2 < 0 or x1+y1 < x2+y2:
                return (x1,y1)
            else:
                return (x2,y2)

典型运行:

>>> smallestSolution(1001,2743,160485)
(111, 18)

它的工作方式:首先使用扩展欧几里德算法找到d = gcd(a,b)和一个解决方案，(x,y)。所有其他解决方案的形式为 (x+k*v,y-k*u) 其中 u = a/d 和 v = b/d。由于 x+y 是线性的，它没有临界点，因此当 x 尽可能小或 y 时，它在第一象限中最小化> 尽可能小。上面的 k 是一个任意整数参数。通过适当使用 floor 和 ceiling，您可以找到尽可能小的 x 或 y 的整数点尽可能小。只取总和最小的那个。

On Edit:我的原始代码使用了应用于 -x/v 的 Python 函数 math.ceiling。这对于非常大的整数是有问题的。我对其进行了调整，以便仅使用 int 操作来计算上限。它现在可以处理任意大的数字:

>>> a = 236317407839490590865554550063
>>> b = 127372335361192567404918884983
>>> c = 475864993503739844164597027155993229496457605245403456517677648564321
>>> smallestSolution(a,b,c)
(2013668810262278187384582192404963131387, 120334243940259443613787580180)
>>> x,y = _
>>> a*x+b*y
475864993503739844164597027155993229496457605245403456517677648564321

大部分计算发生在扩展欧几里德算法的运行中，该算法已知为 O(min(a,b))。