求解线性方程组

Question

我必须找出一个等式的积分解,ax+by=c这个x>=0和y>=0 和的值(x+y) is minimum.

我知道如果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

使用扩展欧几里得算法和线性丢番图方程理论,不需要搜索.这是一个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尽可能小.拿一个总和最小的那个.

在编辑:我的原始代码使用了math.ceiling应用的Python函数-x/v.对于非常大的整数,这是有问题的.我调整它,以便只使用int操作计算上限.它现在可以处理任意大的数字:

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

大多数计算都是在运行扩展的欧几里德算法时进行的,这种算法是已知的O(min(a,b)).