本文介绍如何通过二次不等式分析与根区间截取，精确计算所有满足 x(x+1) 落在闭区间 [a, b] 内的整数 x 的个数，避免暴力枚举，时间复杂度仅为 o(1)。

本文介绍如何通过二次不等式分析与根区间截取，精确计算所有满足 x(x+1) 落在闭区间 [a, b] 内的整数 x 的个数，避免暴力枚举，时间复杂度仅为 o(1)。

函数 $ f(X) = X(X+1) = X^2 + X $ 是一个开口向上的抛物线，在整数域上严格递增（当 $ X \ge 0 $）和严格递减（当 $ X \le -1 $）——但注意：它关于 $ X = -\frac{1}{2} $ 对称，且在负半轴也呈现“镜像递增”特性（例如 $ f(-3)=6,\ f(-2)=2,\ f(-1)=0,\ f(0)=0,\ f(1)=2 $），因此不能简单按单调性二分整个整数轴。正确思路是将约束条件转化为两个二次不等式：

• 下界约束：$ X(X+1) \ge A \quad \Leftrightarrow \quad X^2 + X - A \ge 0 $
• 上界约束：$ X(X+1) \le B \quad \Leftrightarrow \quad X^2 + X - B \le 0 $

由于二次函数连续，满足 $ f(X) \in [A, B] $ 的整数 $ X $ 恰好是同时满足上述两式的整数交集。关键观察在于：

✅ $ X^2 + X - B \le 0 $ 的解集是一个闭区间 $[r{B,\min},\ r{B,\max}]$（因判别式 $ \DeltaB = 1 + 4B \ge 0 $ 在 $ B \ge -1 $ 时恒成立；若 $ B ❌ $ X^2 + X - A {A,\min},\ r_{A,\max}) $，其整数补集（相对于上界区间）即为所求。

因此，算法步骤如下：

1. 求解 $ x^2 + x - B = 0 $ 得实根 $ r{B,1} \le r{B,2} $，则所有候选 $ X $ 必须满足 $ X \in [\lceil r{B,1} \rceil,\ \lfloor r{B,2} \rfloor] $；
2. 求解 $ x^2 + x - A = 0 $ 得实根 $ r{A,1} \le r{A,2} $，则需排除所有满足 $ X \in (r{A,1},\ r{A,2}) $ 的整数 $ X $（即严格使 $ f(X)
3. 最终答案 = count(上界整数区间) − count(上界区间 ∩ 下界开区间内的整数)。

注意边界处理细节：

• 若判别式为负（如 $ B
• ceil(r_min) 和 floor(r_max) 确保包含端点处可能的整数解；
• 排除时不能简单用 range(ceil(rA1)+1, floor(rA2))，因为根可能为整数（如 $ A=0 $ 时根为 $ -1 $ 和 $ 0 $），此时 $ f(-1)=f(0)=0 $，不应被排除；正确做法是：先取 $ X \in [\lceil r{A,1} \rceil,\ \lfloor r{A,2} \rfloor] $，再剔除其中使 $ f(X) = A $ 的点——但更简洁的方式是：仅排除满足 $ f(X) ，这可通过构造开区间整数集合实现。

以下是完整、鲁棒、可直接运行的 Python 实现：

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 (min(root1, root2), max(root1, root2))

def integers_in_closed_interval(r1: float, r2: float) -> set[int]:
    """Return all integers x such that r1 <= x <= r2"""
    if r1 > r2:
        return set()
    return set(range(ceil(r1), floor(r2) + 1))

def integers_in_open_interval(r1: float, r2: float) -> set[int]:
    """Return all integers x such that r1 < x < r2"""
    if r1 >= r2:
        return set()
    # smallest integer > r1 is floor(r1) + 1
    # largest integer < r2 is ceil(r2) - 1
    low = floor(r1) + 1
    high = ceil(r2) - 1
    return set(range(low, high + 1)) if low <= high else set()

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

    # Solve X² + X - B <= 0 → X ∈ [rB1, rB2]
    roots_B = find_quadratic_roots(1, 1, -B)
    if roots_B is None:
        return 0
    candidates = integers_in_closed_interval(*roots_B)

    # Solve X² + X - A < 0 → X ∈ (rA1, rA2); these must be excluded
    roots_A = find_quadratic_roots(1, 1, -A)
    if roots_A is None:
        return len(candidates)  # no X satisfies f(X) < A → all candidates valid

    to_exclude = integers_in_open_interval(*roots_A)
    return len(candidates - to_exclude)

✅ 验证示例：

• solution(0, 2) → candidates from $ X^2+X\le2 $: $ X\in[-2,1] $ → {-2,-1,0,1}；排除 $ X^2+X
• solution(6,6) → $ f(X)=6 $ 当且仅当 $ X=-3 $ 或 $ X=2 $；candidates = {-3,2}，而 $ f(X)

⚠️ 注意事项：

• 浮点精度可能导致 ceil/floor 边界偏差（尤其当根接近整数时），生产环境建议使用 math.isclose 或整数校验（如对候选 X 显式计算 $ X(X+1) $ 验证）；
• 本解法时间复杂度 $ O(1) $，空间复杂度 $ O(1) $（集合大小至多为 $ O(\sqrt{B}) $，但实际受限于根间距，通常极小）；
• 若需返回具体 X 值而非计数，只需将 candidates - to_exclude 转为排序列表即可。

该方法兼顾数学严谨性与工程实用性，是解决此类二次整数约束计数问题的标准范式。