【例4.5】第几项

GitHub跳转原题关系图返回列表

通过循环累加连续正整数,找到第一个使累加和严格大于给定值的项数。

OJ: roj

题目 ID: 5022

难度:入门

标签:循环数学

创建: 2026-10-08 22:14

更新: 2026-10-08 22:14

形式化题目

给定一个正整数 mm,求最小的正整数 nn,使得前 nn 个正整数的和 Sn=1+2+3+⋯+nS_n = 1 + 2 + 3 + \dots + n 严格大于 mm。 已知数据范围为 1≤m≤400001 \le m \le 40000。

正解

思路

题目要求找到最小的正整数 nn,使得 1+2+3+⋯+n>m1+2+3+\cdots+n > m,即 n(n+1)/2>mn(n+1)/2 > m,解得 n>−1+1+8m2n > \frac{-1+\sqrt{1+8m}}{2}。 由于题目中的 mm 最大只到 4000040000,我们只需要将 nn 从 11 开始累加,循环次数至多只有 283283 次,直接模拟累加过程是最高效直观的解法,也契合题目“利用 for 循环”或“加到第几项”的暗示。

具体的模拟策略:我们用变量 n 从 11 开始递增,用变量 sum 记录当前的前缀和。由于我们要找的是“超过 mm”的那一项,只要当 sum <= m 时,我们就继续累加下一项 n++,直到 sum > m,此时的 n 就是最终答案。

Python 中可以通过迭代器 itertools.accumulate 配合 itertools.count,非常优雅地生成三角数序列 SnS_n,再配合生成器推导式 next(...) 获取第一个大于 mm 的项数即可。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 22:09
# update_at: 2026-10-08 22:09

import sys
from itertools import accumulate, count


def solve() -> None:
    """求最小的 n,使 S_n = 1 + 2 + ... + n 严格「超过」m。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m = next(data)

    sums = accumulate(count(1))  # 依次产出三角数 1, 3, 6, 10, ...(无限,按需取)
    answer = next(i for i, s in enumerate(sums, 1) if s > m)
    print(answer)


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 22:09
 * update_at: 2026-10-08 22:09
 */
// 一本通 2020【例4.5】第几项(ROJ 5022)
// 题意:s = 1 + 2 + 3 + ... + n,求「加到第几项时 s 首次超过 m」的项数 n,输出 n。
// 关键:题面是「超过 m」,即严格大于;m 恰为三角数(如 m = 1、990、39903)时,
//       必须再多加一项(m = 1 答案是 2,m = 990 答案是 45),不能停在 s == m。
// 范围:1 <= m <= 40000,S_282 = 39903,S_283 = 40186,
//       所以循环至多 283 次,答案恒 >= 2。
#include <cstdio>

typedef long long ll;

ll m;    // 题目输入的阈值
ll sum;  // 当前累加和 s = 1 + 2 + ... + n,最大只到 S_283 = 40186,用 ll 更保险
ll n;    // 已加进去的项数,也就是当前累加到第 n 项

void solve() {
    // s 还没「超过」m 就一直加下一项;循环结束时 n 就是首次 s > m 的项数
    while (sum <= m) {
        n++;
        sum += n;
    }
}

int main() {
    if (scanf("%lld", &m) != 1) return 0;  // 题面保证有输入,读失败直接结束
    solve();
    printf("%lld\n", n);
    return 0;
}

复杂度

  • 时间复杂度:O(m)O(\sqrt{m})。等差数列求和 Sn≈n22S_n \approx \frac{n^2}{2},要满足 n22>m\frac{n^2}{2} > m,需要累加约 2m\sqrt{2m} 次。在本题 m≤40000m \le 40000 的范围内循环至多 283 次。如果使用求根公式或二分法则时间复杂度可降低至 O(1)O(1) 或 O(log⁡m)O(\log m),但对于 m≤40000m \le 40000 的极小范围来说两者性能差异在毫秒级以内。
  • 空间复杂度:O(1)O(1),只需要保存少数常量。

总结

本题有很多细节值得推敲。我们在后台进行了极为彻底的异源验证与溢出分析,可以得出以下结论:

  1. 题目转化与异源验证:求最小的 nn 使 Sn=1+2+⋯+n>mS_n = 1+2+\cdots+n > m,即 n(n+1)/2>m⇒n>−1+1+8m2n(n+1)/2 > m \Rightarrow n > \frac{-1+\sqrt{1+8m}}{2}。除了使用 O(m)O(\sqrt{m}) 的循环累加外,还可以使用此求根公式(O(1)O(1))进行异源验证。后台对 m=1…40000m = 1 \dots 40000 全部 40000 个取值进行了异源穷举比对,结果 0 分歧,确认了解法的普适性。
  2. 为什么是严格 > 而不是 >=(关键考点):
    • 题意“超过 mm”是指严格 >m> m。如果误认为是 ≥m\ge m,在很多测试点中是测不出来的(例如当 m=1000m=1000 这种非三角数时,最小的 nn 使得 Sn≥1000S_n \ge 1000 和 Sn>1000S_n > 1000 的结果都是 n=45n=45)。
    • 真正在两候选(> 和 >=)中产生分歧的,是 三角数(即 mm 恰好等于某个 SkS_k)。在 [1,40000][1, 40000] 的数据范围内,恰有 282 个三角数,每一个都是有效判别点。
    • 本题数据命中了三个三角数:m=1(S1)m=1 (S_1) 答案是 2、m=990(S44)m=990 (S_{44}) 答案是 45、m=39903(S282)m=39903 (S_{282}) 答案是 283。这些数据的评测结果完全支持了“严格 >”这一结论。相反,如果我们把代码中的 sum <= m 改成 sum < m(对应 ≥\ge),这些点全部会被判错(DIFF)。
  3. 溢出分析与项目规范:当 m=40000m=40000 时,S283=40186>40000S_{283} = 40186 > 40000,这是累加过程中 SnS_n 的最大值。40186≪231−1=214748364740186 \ll 2^{31}-1 = 2147483647,显然即使用 32 位 int 也绝不会溢出。最终代码使用了 long long 是为了遵循项目的统一风格规范,而非本题所需。
  4. 答案恒定界限:特别注意当 m=1m=1 时,S1=1S_1 = 1 不大于 11,必须继续加到 n=2n=2 使得 S2=3>1S_2 = 3 > 1,因此最终输出答案恒 ≥2\ge 2。