22509: 解方程

http://cs101.openjudge.cn/practice/22509/

求解方程 x^2 + x + 1 + log2(x) = y ，这里log2表示以2为底的对数，x^2是x的平方。对于输入的正整数y，求x

输入

多组测试用例，每组一行，为一个正整数y(10≤y≤100000000)

输出

对于每组测试用例，输出解x(四舍五入精确到小数点后4位)

样例输入

10
49

样例输出

2.3333
6.2532

提示

计算log2可使用代码: from math import log2

来源：陈鑫

要解决这个问题，需要找到方程 x^2 + x + 1 + log2(x) = y 的数值解。这不是一个可以解析求解的方程，因此需要使用数值方法来寻找解，比如牛顿法或者二分查找法。

由于 x > 0（因为 log2(x) 在 x <= 0 时是未定义的），且函数 x^2 + x + 1 和 log2(x) 都是单调增加的，我们可以利用这一点使用二分查找法在一个足够大的区间内查找解。

下面是一个使用二分查找法来求解方程的 Python 实现：

from math import log2

def find_x(y):
    # 定义方程
    def equation(x):
        return x**2 + x + 1 + log2(x)

    # 二分查找解
    left, right = 0, y  # x的解显然在0和y之间，因为当x=y时，x^2 + x + 1 + log2(x) > y
    while right - left > 1e-8:  # 精确到小数点后8位
        mid = (left + right) / 2
        if equation(mid) < y:
            left = mid
        else:
            right = mid
    return (left + right) / 2

# 主程序开始
# 读取输入并计算答案
results = []
try:
    while True:
        y = int(input())
        x = find_x(y)
        results.append(x)
except EOFError:
    pass

# 输出结果
for x in results:
    print(f"{x:.4f}")

这段代码首先定义了要解的方程，然后通过二分查找法查找方程的根。最后，它读取输入并输出每个输入 y 对应的解 x，四舍五入到小数点后四位。输入是通过标准输入连续提供的，直到 EOF（文件结束符）。

由于方程的解对于给定的 y 是唯一的，二分查找在这里是适合且高效的方法。