用于计算具有两个变量的单个简单方程的解集的算法

algorithm math java

2022-09-04 20:43:06

假设我有一个简单的等式：

7x + 4y = n

其中 n 由我们选择，x、y 和 n 都是正整数。这是给我们的唯一等式。在可能的解决方案中，我们需要x最小的解决方案（x，y）。例如：

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）。有没有更好的算法来计算解决方案？

答案 1

让我们考虑更普遍的问题

对于两个共素正整数和给定一个正整数，找到一对非负整数，使得具有最小值。（如果有。不需要，例如没有非负和的解决方案。abn(x,y)a*x + b*y = nx7*x + 4*y = 5xy

暂时忽略非阴性，给定任何解决方案

a*x0 + b*y0 = n

所有解都具有某个整数的形式。所以模和模的其余部分是解的不变数，我们有(x0 - k*b, y0 + k*a)kxbya

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

因此，我们需要解决方程式 - 另一个紧随其后。a*x ≡ n (mod b)

设为具有的整数。例如，您可以通过扩展的欧几里得算法找到它，或者（等效地）在O（log b）步骤中连续分数展开。这两种算法自然会产生具有该属性的唯一性。0 < ca*c ≡ 1 (mod b)a/bc < b

则的最小候选项是模的余数。xx0n*cb

问题有一个非负的解，当且仅当，然后是出现在任何具有非负和的解中的最小非负解。xyx0*a <= nx0xxy

当然，对于小的和像7和4一样，蛮力并不比计算模的反函数慢。abab

答案 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。