如何从函数f(n)=An²+Bn+C 中找到第一个完全平方数？给出了 B 和 C。 A,B,C 和 n 总是整数，A 总是 1。问题是找到 n。
示例:A=1，B=2182，C=3248
第一个完全平方的答案是 n=16，因为 sqrt(f(16))=196。
我的算法递增 n 并测试平方根是否为整数。
当 B 或 C 很大时，此算法非常慢，因为需要 n 次计算才能找到答案。
是否有更快的方法来进行此计算？是否有一个简单的公式可以得出答案？
最佳答案
您正在寻找的是一般二次丢番图方程的特例的整数解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])，您甚至可以找到一个实现 here包括 source code和 method of solution 的解释.
1:您可能将其识别为 conic section .它是，人们已经studying them for thousands of years .因此，我们对他们的了解很深，你的问题其实也很出名。对它们的研究是一个immensely deep and still active area of mathematics .
关于algorithm - 有效地找到一个完美的广场，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9114874/