如何精确求解具有大整数系数的二次方程(整数)？

Question

我在Google Code Jam中读到了关于bullseyes的问题.(比赛结束了,所以可以谈谈)

玛丽亚以t毫升的黑色涂料开始,她将用它来绘制厚度为1厘米(1厘米)的戒指.厚度为1cm的环是两个同心圆之间的空间,半径相差1cm.

玛丽亚在半径为r cm的白色圆圈周围绘制了第一个黑色环.

半径为1cm的圆盘面积为πcm2.需要1毫升涂料来覆盖面积πcm2.玛丽亚可以画出的最大黑圈数量是多少？

通过我在纸上的计算,用n个环绘制一个靶心的油漆区域,内半径r,作为pi的倍数是 2*n**2 + n*(2*r-1)

因此,给定t*pi毫升的涂料,问题是找到最大的n f(n,r) <= t.

今天早上我用二进制搜索解决了这个问题https://github.com/hickford/codejam/blob/master/2013/1A/bullseye/bu​​llseye.py

我选择二次搜索而不是二次方程,因为我非常担心浮点不精确 - 在这个问题中,t和r是10**18的整数.算术不精确使我在之前的Code Jam中找到了位置.

但我很好奇.你能否支持二次方程给出具有大整数系数的方程的正确答案？像Sympy或Numpy这样的数学图书馆能为我提供什么吗？

---

演示二次方程给出大输入的错误答案.例如,用r=308436464205151562和t=1850618785230909388.要求的二次方程是

2*n**2 + 616872928410303123*n -1850618785230909388 <= 0

即.系数是

a = 2
b = 616872928410303123
c = -1850618785230909388

用Python计算

    > int((-b + math.sqrt(b**2 - 4*a*c)) / (2*a))
    0

这是错误的答案!正确的答案(通过二分搜索找到)是3

>>> n = 3
>>> 2*n**2 + 616872928410303123*n -1850618785230909388 <= 0
True

Answer 1

对于符号精确操作，有sympy。

如果您粘贴以下内容：

a, b, c = 2, 616872928410303123, -1850618785230909388
x = Symbol('x')
int(max(solve(a*x**2 + b*x + c, x)))

在这里，你得到 3。

[编辑以下OP评论]。