计算两个变量单个简单方程解集的算法

Question

假设我有一个简单的形式方程式:

7x + 4y = n

其中n由我们选择,x,y和n都是正整数.这是给我们的唯一方程式.在可能的解决方案中,我们需要解决方案(x,y),其中x是最小的.例如

7x + 4y = 14, then (2, 0) is the solution
7x + 4y = 15, then (1, 2) is the solution
7x + 4y = 32, then (4, 1) and (0, 8) are the possible solutions,
of which (0, 8) is the correct solution

我想设计一种算法,以尽可能少的运行时间来计算它.我想到的当前算法是这样的:

Given an input n
Calculate max(x) = n/7
for i = 0 to max(x)
    If the equation 7*i + 4*y = n holds
        return value of i and y
    else
        continue

我认为,该算法在最坏情况下的行为可以具有高达O(n)的运行时间.有没有更好的算法来计算解决方案？

Answer 1

让我们考虑更普遍的问题

• 对于两个互质正整数,a并且b给定正整数n,找到一(x,y)对非负整数,使得a*x + b*y = n最小x.(如果存在的话.不必有,例如7*x + 4*y = 5与非负无解x和y.)

在任何解决方案的情况下,暂时不考虑非负性

a*x0 + b*y0 = n

所有解决方案都具有(x0 - k*b, y0 + k*a)某种整数的形式k.因此x模数b和y模数的余数a是解的一个不变量,而且我们有

a*x ? n (mod b), and b*y ? n (mod a)

所以我们需要解决方程式a*x ? n (mod b)- 另一个方法如下.

我们0 < c是一个整数a*c ? 1 (mod b).例如,您可以通过扩展的欧几里德算法找到它,或者(等效地)a/b在O(log b)步骤中继续分数扩展.两种算法都自然地产生了c < b该属性的唯一性.

然后最小的候选人x是余数x0的n*c模b.

该问题与非负的解决方案x,并y当且仅当x0*a <= n,然后x0是最小非负x出现在与nonnegtaive任何解决方案x和y.

当然,对于小型a和b类似7和4,蛮力并不比计算a模的倒数慢b.

Answer 2

我们有

7(x-4)+4(y+7)=7x+4y

因此,如果(x,y)是一个解,那么(x-4,y + 7)也是一个解.因此,如果有一个解决方案,那么有一个x <4.这就是为什么你只需要测试在恒定时间内运行的x = 0..3.

这可以扩展到ax + by = n形式的任何方程式,您只需要测试x = 0..b-1.