c++ - 以优于 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会导致 requiredy为整数，但即使不这样做，我们也已从 O(N ² ) 移动到 O(N)，这很可能有足够的时间在更合理的时间范围内完成任务。

---

1. 当然，如果为b0，则项为 0 ，by所以ax = c我们有正确的。x = c/axxyc