技术问询：求解满足X*(X+1)∈[A,B]的整数X的个数

问题描述 #

给定整数A和B，统计所有满足X*(X+1)落在闭区间[A, B]内的整数X的个数。

解题思路 #

将原条件转化为二次不等式组：

• (X^2 + X \geq A) 等价于 (X^2 + X - A \geq 0)
• (X^2 + X \leq B) 等价于 (X^2 + X - B \leq 0)

计划步骤：

1. 利用下方的find_quadratic_roots()函数求解上述两个二次方程的根。
2. 通过两个方程的根范围推导所有符合条件的正、负整数X（此步骤存在困惑）

代码实现框架 #

from math import sqrt, floor, ceil

def find_quadratic_roots(a: int, b: int, c: int) -> tuple:
    """ 返回二次方程ax² + bx + c = 0的根
    本次问题中a和b固定为1 """

    discriminant = b*b - 4*a*c
    if discriminant < 0:
        return None
    
    root1 = (-b + sqrt(discriminant)) / (2*a)
    root2 = (-b - sqrt(discriminant)) / (2*a)

    return (min(root1, root2), max(root1, root2))


def solution(A: int, B: int) -> int:
    if A > B:  return 0
        
    # 处理下界条件：x² + x - A ≥ 0
    lower_roots = find_quadratic_roots(1, 1, -A)
    
    # 处理上界条件：x² + x - B ≤ 0
    upper_roots = find_quadratic_roots(1, 1, -B)
    

assert solution(-1, 0) == 2    # 符合条件的X：-1, 0
assert solution(0, 0) == 2     # 符合条件的X：-1, 0
assert solution(0, 1) == 2     # 符合条件的X：-1, 0
assert solution(0, 2) == 4     # 符合条件的X：-2, -1, 0, 1
assert solution(-5, 5) == 4    # 符合条件的X：-2, -1, 0, 1
assert solution(0, 6) == 6     # 符合条件的X：-3, -2, -1, 0, 1, 2
assert solution(6, 6) == 2     # 符合条件的X：-3, 2
assert solution(3, 6) == 2     # 符合条件的X：-3, 2

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