解方程算法：x^2 - 4y^2 = n

Question

最近，我参加了一场包含编程作业的面试。其中一个作业是：
编写一个函数，找到所有的整数值对x，y，使得给定的整数n解决方程：x^2 - 4y^2 = n 我的方法是： 我为y重写了这个方程：y = sqrt(x^2 - n) / 2
从x=sqrt(n)到x=n进行循环
对于每个x，我计算了y的值，并检查y是否为整数。

这个解决方案给出了正确的答案，但是对于大的n，这个算法没有满足性能要求。
在作业中还提供了提示：x^2 - 4y^2 = (x - 2y)(x + 2y)，但我不知道如何使用这个提示来解决这个问题。

只是出于好奇（现在作业已经结束），有什么办法可以以最优的方式解决这个问题吗？

- Michał Herman

---

这似乎不是编程问题，而更像是数学问题，因此也许 math.stackexchange.com 更适合回答这个问题。 - Ulrich Eckhardt

你能给出样本输入/输出和实际限制条件吗？ - Ajay Gaur

"sqrt" 只返回正值，因此 1. 您还必须检查 "x" 的负值，2. 您必须否定 "sqrt" 返回的每个 "y" 值，以便获得问题的完整答案。您的解决方案是部分的。 - mangusta

Answer 1

提示“x ^ 2-4y ^ 2 =（x-2y）（x + 2y）”意味着n必须被“（x-2y）”和“（x + 2y）”整除。 因此，例如，对n进行整数分解会产生一组相对较小的整数，可以搜索这些整数是否可以生成“（x-2y）”和“（x + 2y）”形式的数字。

只考虑正整数“x”和“y”就足够了，因为由于方程中的平方，每个“x”也都有一个解“-x”，“y”的情况也是如此。 因此，您找到的每对数字实际上会给您提供四个不同的解。

---

您还可以查看丢番图方程理论，这是这种问题背后的一般数学理论。 您的特殊情况在MathWorld文章中得到了解决。

- piripiri

---

还有一种特殊情况，当 n = 0 时，有无限多个解：对于所有整数值的 i，(x, y) = (2 i, i)。 - r3mainer

Answer 2

在你的方法中，你需要循环从sqrt(n)到n。这意味着你的解决方案的时间复杂度为O(n)。

如果我们对负数解感兴趣，我们可以通过给定非负的一对(x, y)来创建3个解：(-x, y)，(x, -y)和(-x, -y)（由于x或y可能是0，因此这些解不一定是不同的）。所以我们可以限制x和y为非负数。我也假设n > 0。

现在假设a = x - 2y并且b = x + 2y。由于y >= 0，所以a <= b。

然后，a * b = n，并且b = n / a。

我们现在可以循环遍历所有a值，其中1 <= a <= sqrt(n)，并检查是否存在整数b = n / a。（如果a大于sqrt(n)，则b = n / a将小于a。）

对于所有b为整数的a值，我们计算x = (a + b) / 2和y = (b - a) / 4。如果x和y是整数，则我们有一个解决方案。

这个算法的时间复杂度是O(sqrt(n))。

- heijp06