求满足x²+x≤y的最大非负整数x的高效实现方案咨询

原来的分段遍历方案属于暴力枚举思路，时间复杂度为O(n)，当y达到1e17级别时完全无法在规定时间内跑完，且代码冗余度极高。由于x² + x的值随x增大严格单调递增，完全满足二分查找的适用条件，用二分法可以把时间复杂度压到O(log y)级别，最多执行30余次循环就能得到结果。

• 禁止使用math模块、幂运算符、round函数，因此直接用乘法计算mid*mid + mid即可，Python原生支持大整数运算不需要担心溢出
• 右边界直接设为2000000000即可覆盖所有y≤1e17的情况（1e17的平方根约为3.16e8，远小于2e9）

integer_y = int(input())
left = 0
right = 2000000000
result = 0
while left <= right:
    mid = (left + right) // 2
    current_val = mid * mid + mid
    if current_val <= integer_y:
        # 当前mid符合条件，尝试找更大的解
        result = mid
        left = mid + 1
    else:
        # mid太大，缩小右边界
        right = mid - 1
print(result)

输入示例的100000000000000000时，程序输出结果为316227765，完全符合题目要求，且所有边界情况（比如y=0输出0、y=2输出1等）都能正确处理。

内容的提问来源于stack exchange，提问作者Pancake