级数求和

题目描述

已知 $S_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$ 。对于任意整数 $k$ ，当 $n$ 足够大时 $S_n > k$ 。给定整数 $k\ (1 \leqslant k \leqslant 15)$ ，求最小的 $n$ 使得 $S_n > k$ 。

输入：一个整数 $k$ 。输出：一个整数 $n$ 。

样例输入： $k=1$ ，此时 $S_1=1 \leqslant 1$ 、 $S_2=1.5>1$ ，故输出 $2$ 。

text

样例输出：

text

思路

$S_n$ 每步加上正数，严格递增且发散，所以从 $n=1$ 起逐项累加，和首次大于 $k$ 时的 $n$ 就是最小答案。由 $S_n \approx \ln n + \gamma$ 知 $k \leqslant 15$ 时答案不超过约 $1.8 \times 10^6$ ，直接用 double 循环即可。

参考代码

Python 版：

python

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

import sys


def solve() -> None:
    k = int(sys.stdin.buffer.read())
    total = 0.0          # 累计的调和级数 S_n
    n = 0
    while total <= k:    # 逐项累加，首次超过 k 的 n 即答案
        n += 1
        total += 1 / 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/**
 * 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-05 00:39
 * update_at: 2026-10-05 00:39
 */

#include <cstdio>

typedef long long ll;

// 调和级数单调递增，逐项累加，首次超过 k 的 n 就是最小答案
int main() {
    ll k;              // 阈值 1 <= k <= 15
    double total = 0;  // 累计的调和级数和 S_n

    scanf("%lld", &k);

    ll n = 0;          // 已累加的项数
    while (total <= k) {
        n++;
        total += 1.0 / (double)n; // 加上第 n 项 1/n
    }

    printf("%lld\n", n);
    return 0;
}

目录

题目描述

思路

参考代码