解方程的算法 : 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)，但我不知道如何使用此提示来解决该问题.

出于好奇(因为作业现在已经结束)，有什么想法可以以最佳方式解决这个问题吗？

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。因此，您找到的每一对数字实际上都为您提供了四种不同的解决方案。

---

您可能还想查看 Diophantine equations 的理论，这就是这类问题背后的一般数学理论。您的特殊情况在 MathWorld article 中得到解决。 .