algorithm - 有效地找到一个完美的正方形

Question

如何从函数中找到第一个完美正方形：f(n)=An²+Bn+C？给出了 B 和 C。A,B,C 和 n 总是整数，而 A 总是 1。问题是找到 n。

Example: A=1, B=2182, C=3248

第一个完美正方形的答案是 n=16，因为sqrt(f(16))=196.

我的算法增加 n 并测试平方根是否为整数。

当 B 或 C 很大时，该算法非常慢，因为需要 n 次计算才能找到答案。

有没有更快的方法来做这个计算？有没有一个简单的公式可以得出答案？

Answer 1

您正在寻找的是一般二次丢番图方程^{1的特殊情况的整数解}

Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0

你在哪里

ax^2 + bx + c = y^2

因此，A = a, B = 0, C = -1, D = b, E = 0, F = c其中a, b,c是已知整数，并且您正在寻找未知数x并且y满足该等式。一旦你认识到这一点，这个普遍问题的解决方案就会很多。Mathematica 可以做到（使用Reduce[eqn && Element[x|y, Integers], x, y]），您甚至可以在这里找到一个实现，包括源代码和解决方法的说明。

¹：你可能会认出这是一个圆锥曲线。确实如此，人们已经研究了数千年。因此，我们对它们的理解非常深刻，您的问题实际上非常有名。对它们的研究是一个非常深入且仍然活跃的数学领域。