[NOIP2002-普及]级数求和

题目描述

已知 $S_n = 1 + \frac12 + \frac13 + \dots + \frac1n$ 。给定整数 $K$ （ $1 \le K \le 15$ ），求最小的正整数 $n$ 使得 $S_n > K$ 。

输入格式：一个正整数 $K$
输出格式：一个正整数 $n$

样例输入：1
样例输出：2

思路

调和级数严格递增且发散，直接从 $n=1$ 开始逐项累加 $\frac1n$ ，维护部分和 $s$ ，当 $s > K$ 时当前的 $n$ 即为答案。 $K \le 15$ 时答案不超过约 $3.3 \times 10^6$ ，直接模拟即可通过。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#!/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-02 04:40
# update_at: 2026-10-02 04:40

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    k = next(data)  # 输入只有一个整数 K

    s = 0.0  # S_n = 1 + 1/2 + ... + 1/n，严格递增
    n = 0
    while s <= k:  # 边加边判：S_n 一旦超过 K 就停
        n += 1
        s += 1.0 / n

    print(n)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30/**
 * 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-06 12:31
 * update_at: 2026-10-06 12:31
 */

#include <iostream>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    cin >> k;

    double s = 0.0; // 当前调和级数部分和 S_n
    int n = 0;      // 当前项数
    while (s <= k) { // 严格大于 K 时停止
        ++n;
        s += 1.0 / n;
    }

    cout << n << "\n";
    return 0;
}

[NOIP2002-普及]级数求和

目录

题目描述

思路

参考代码