求给定区间内可分解为连续整数乘积的整数个数及解法优化问询

你的解法思路正确，但存在明显的效率瓶颈：当区间[a,b]范围很大时（比如b-a达到百万级别甚至更大），遍历每个数的时间成本会急剧上升。我们可以通过数学推导直接定位符合条件的数，将时间复杂度从O(b-a)优化到O(1)。

核心数学原理 #

若正整数n能表示为两个连续整数的乘积，即n = x(x+1)（x为正整数），对等式变形可得：

4n + 1 = 4x² + 4x + 1 = (2x+1)²

这意味着：4n+1必须是一个完全平方数，且该平方数的平方根为奇数——这是n满足条件的充要条件。

更关键的是，每个合法的x对应唯一的n，反之亦然。因此我们不需要遍历区间内的所有数，只需计算满足a ≤ x(x+1) ≤ b的正整数x的个数即可。

推导x的取值范围 #

1. 求最小x：解不等式x(x+1) ≥ a，对应二次方程x² + x - a = 0的正根为：

   x = [-1 + √(1 + 4a)] / 2
   

   取该值的向上取整作为最小x，同时因为x是正整数，若计算结果小于1，则最小x取1（x=1时n=2，是最小的符合条件的数）。

2. 求最大x：解不等式x(x+1) ≤ b，对应二次方程x² + x - b = 0的正根为：

   x = [-1 + √(1 + 4b)] / 2
   

   取该值的向下取整作为最大x。

3. 计算个数：若最大x ≥ 最小x，则个数为maxX - minX + 1；否则区间内没有符合条件的数，返回0。

优化后的Java代码 #

public int solve(int a, int b) {
    // 计算最小x的下界
    double lowerRoot = Math.sqrt(1 + 4.0 * a);
    int minX = (int) Math.ceil((-1 + lowerRoot) / 2);
    minX = Math.max(minX, 1); // x至少为1，对应n=2

    // 计算最大x的上界
    double upperRoot = Math.sqrt(1 + 4.0 * b);
    int maxX = (int) Math.floor((-1 + upperRoot) / 2);

    // 处理无符合条件数的情况
    return maxX >= minX ? maxX - minX + 1 : 0;
}

关键细节说明 #

• 使用4.0 * a而非4 * a，避免int类型溢出（当a为较大int值时，4*a可能超出int的取值范围）。
• 边界处理：当a≤2时，最小x直接取1，因为x=1对应的n=2是最小的符合条件的数。
• 测试验证：比如区间[2,6]，计算得minX=1，maxX=2，返回2，对应2=1×2、6=2×3，结果正确。

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