高效求解满足 X(X+1) ∈ [A, B] 的整数 X 个数的数学与编程方法-Python教程-PHP中文网

高效求解满足 X(X+1) ∈ [A, B] 的整数 X 个数的数学与编程方法

本文介绍如何通过二次不等式分析与根区间截取，精确计算所有整数 x，使得 x(x+1) 落在闭区间 [a, b] 内；核心是利用求根公式确定可行 x 的连续整数范围，并通过集合差集排除边界外值。

本文介绍如何通过二次不等式分析与根区间截取，精确计算所有整数 x，使得 x(x+1) 落在闭区间 [a, b] 内；核心是利用求根公式确定可行 x 的连续整数范围，并通过集合差集排除边界外值。

要解决“求满足 $ X(X+1) \in [A, B] $ 的整数 $ X $ 的个数”这一问题，关键在于将乘积形式转化为标准二次不等式，并借助实数根界定整数解的合法区间。

由于 $ X(X+1) = X^2 + X $，原条件等价于： $$ A \leq X^2 + X \leq B $$ 这可拆分为两个不等式：

$ X^2 + X - A \geq 0 $ → 要求 $ X $ 不在两根之间的开区间（即取外部或边界）；
$ X^2 + X - B \leq 0 $ → 要求 $ X $ 落在两根之间的闭区间（含端点）。

但直接处理“外部解”易出错（尤其跨正负区间时），更稳健的策略是：
✅ 先求出所有满足上界约束 $ X^2 + X \leq B $ 的整数 $ X $（记为集合 $ SB $）；
✅ 再从中剔除那些严格不满足下界的 $ X $，即满足 $ X^2 + X { ✅ 最终答案即为 $ |SB \setminus S{

为此，我们定义辅助函数 integers_between_roots(roots)，它接收二次方程 $ x^2 + x + c = 0 $ 的实数根（小根在前），返回所有落在 $ [\lceil r_1 \rceil,\ \lfloor r_2 \rfloor] $ 内的整数构成的 range（注意：range 左闭右开，故需 +1 保证包含 floor(r2)）：

from math import sqrt, floor, ceil

def find_quadratic_roots(a: int, b: int, c: int) -> tuple | None:
    discriminant = b * b - 4 * a * c
    if discriminant < 0:
        return None
    sqrt_d = sqrt(discriminant)
    root1 = (-b - sqrt_d) / (2 * a)
    root2 = (-b + sqrt_d) / (2 * a)
    return (root1, root2)  # already ordered: smaller first

def integers_between_roots(roots: tuple) -> range:
    r1, r2 = roots
    return range(ceil(r1), floor(r2) + 1)

主逻辑如下：

若 $ A > B $，无解，直接返回 0；

求 $ x^2 + x - B = 0 $ 的根 → 得到所有满足 $ X(X+1) \leq B $ 的整数集合 $ S_B $；

求 $ x^2 + x - A = 0 $ 的根 → 得到所有满足 $ X(X+1) \leq A $ 的整数集合 $ S_{\leq A} $；

但我们需要剔除的是 $ X(X+1) 0+1) = A $，它应被保留。因此，$ S

{

然而，原答案中“values_below_A = values_below_or_at_A - set(roots_of_a)”存在严重缺陷：roots_of_a 是浮点数元组，不能直接转为 set，且即使能，减去根也无法准确剔除整数点（因根通常非整数）。正确做法是：对下界使用 $ A-1 $ 构造新不等式，即：

满足 $ X(X+1)

因此优化后的 solution 实现如下：

def solution(A: int, B: int) -> int:
    if A > B:
        return 0

    # All X such that X(X+1) <= B
    roots_b = find_quadratic_roots(1, 1, -B)
    if roots_b is None:
        return 0
    s_b = set(integers_between_roots(roots_b))

    # All X such that X(X+1) < A  <=> X(X+1) <= A-1
    roots_a_minus = find_quadratic_roots(1, 1, -(A - 1))
    if roots_a_minus is None:
        return len(s_b)  # no X satisfies X(X+1) < A → all in s_b are valid

    s_less_than_a = set(integers_between_roots(roots_a_minus))

    return len(s_b - s_less_than_a)

? 注意事项：

浮点精度可能导致 ceil/floor 边界偏差（如根非常接近整数时）。实际工程中建议对候选边界点 $ \lfloor r_2 \rfloor $、$ \lceil r_1 \rceil $ 做±1校验，或改用整数二分搜索避免浮点误差；
当 $ A $ 极小（如负大数）时，$ A-1 $ 仍有效；该方法无需特殊处理负数区间；
时间复杂度 $ O(1) $，空间复杂度 $ O(\text{number of integer solutions}) $，远优于暴力枚举。

✅ 验证示例：