调和级数求和, 这个题有多种做法,

  1. n较大时, 每隔50个求一次和, 打表, 复杂度O(1e7)内
  2. 近似公式: f(n) ≈ ln(n) + C + 1.0/(2 * n) (欧拉常数C ≈ 0.57721566490153286060651209)
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
31
32
33
34
35



#include <bits/stdc++.h>
using namespace std;
const double C = 0.57721566490153286060651209;

double a[50010];

void init() {
    for (int i = 1; i <= 50010; i++) {
        a[i] = 1.0 / i + a[i - 1];
    }
}

int main() {
    int t;
    int T = 0;
    cin >> t;
    int n;
    //for(int i = 1; i <= n ; i++)
    init();
    while (t--) {
        cin >> n;
        double ans = 0.0;
        if (n <= 50000) {
            ans = a[n];
        }
        else {
            ans = log(n) + C + 1.0 / (2 * n);
        }
        printf("Case %d: %.10lf\n", ++T, ans);
    }
    return 0;
}