以优于 O(n^2) 的时间复杂度找到位于 ax+by=c 线上的所有有序整数对

Question

我正在尝试编写一个可以输入 3 个 long int 变量 a、b、c 的代码。代码应找到所有整数 (x,y) 以便 ax+by = c，但输入值最多可达 2*10^9。我不确定如何有效地做到这一点。我的算法是 O(n^2)，这对于如此大的输入来说真的很糟糕。我怎样才能做得更好？这是我的代码-

typedef long int lint;

struct point
{
lint x, y;
};

int main()
{
lint a, b, c;
vector <point> points;
cin >> c >> a >> b;
for(lint x = 0; x < c; x++)
    for(lint y = 0; y < c; y++)
    {
        point candidate;
        if(a*x + b*y == c)
        {
            candidate.x = x;
            candidate.y = y;
            points.push_back(candidate);
            break;
        }
    }
}

Answer 1

似乎您可以应用一点点非常简单的数学来解决 y 对于任何给定值 x 的问题。从 ax + by = c 开始：

ax + by = c

by = c - ax

假设非零 b¹，然后我们得到：

y = (c - ax) / b

有了它，我们可以在循环中生成 x 的值，将其代入上面的等式，计算 y 的匹配值并检查它是否为整数。如果是，则添加该 (x, y) 对，然后继续 x.

的下一个值

当然，您可以进行下一步，找出 x 的哪些值会导致所需的 y 为整数，但即使不这样做，我们已经从 O(N²) 转移到 O(N)，这可能足以在更合理的时间范围内完成任务。

当然，如果b为0，则by项为零，所以我们有ax = c，然后我们可以将其转化为x = c/a，所以然后我们只需要检查 x 是一个整数，如果是这样，所有 x 与 y 的任何候选值的对将产生正确的 c.

以优于 O(n^2) 的时间复杂度找到位于 ax+by=c 线上的所有有序整数对

Finding all the ordered pairs of integers lying on a line ax+by=c in better than O(n^2) time complexity

c++

linear-equation