【调和级数 && 欧拉常数】 Harmonic Number

Step1 Problem:

原题求f(n)=1/1+1/2+1/3+1/4…1/n (1 ≤ n ≤ 10⁸).，精确到10^-8

Step2 Ideas:

^{调和级数(即f(n))至今没有一个完全正确的公式，但欧拉给出过一个近似公式：(n很大时)}

f(n)≈ln(n)+C+1/2*n

^{欧拉常数值：C≈}^{0.57721566490153286060651209}

也可以用打表水过去。10e8全打表必定MLE，而每40个数记录一个结果，即分别记录1/40,1/80,1/120,...,1/10e8，这样对于输入的每个n，最多只需执行39次运算，大大节省了时间，空间上也够了。

Step3 code：

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<bitset>
 7 #include<cassert>
 8 #include<cctype>
 9 #include<cmath>
10 #include<cstdlib>
11 #include<ctime>
12 #include<deque>
13 #include<iomanip>
14 #include<list>
15 #include<map>
16 #include<queue>
17 #include<set>
18 #include<stack>
19 #include<vector>
20 #define lt k<<1
21 #define rt k<<1|1
22 #define lowbit(x) x&(-x)
23 #define lson l,mid,lt
24 #define rson mid+1,r,rt
25 using namespace std;
26 typedef long long  ll;
27 typedef long double ld;
28 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
29 #define mem(a, b) memset(a, b, sizeof(a))
30 //#define int ll
31 const double pi = acos(-1.0);
32 const double eps = 1e-6;
33 const double C = 0.57721566490153286060651209;
34 const ll mod = 1e9 + 7;
35 const int inf = 0x3f3f3f3f;
36 const ll INF = 0x3f3f3f3f3f3f3f3f;
37 const int maxn = 1e5 + 5;
38 double a[maxn];
39 
40 int main()
41 {
42     a[1] = 1.0;
43     for (int i = 2; i < 1e5; i++) a[i] = a[i - 1] + 1.0 / i;
44     int T;
45     cin >> T;
46     for (int t = 1; t <= T; t++) {
47         cout << "Case " << t << ": ";
48         int n;
49         cin >> n;
50         if (n < 1e5) cout << fixed << setprecision(10) << a[n] << endl;
51         else {
52             double x = log(n) + C + 1.0 / (2.0 * n);
53             cout << fixed << setprecision(10) << x << endl;
54         }
55     }
56     return 0;
57 }

Step4 code2：参考博客

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cmath>
 6 
 7 using namespace std;
 8 
 9 const int maxn = 2500001;
10 double a[maxn] = {0.0, 1.0};
11 
12 int main()
13 {
14     int t, n, ca = 1;
15     double s = 1.0;
16     for(int i = 2; i < 100000001; i++)
17     {
18         s += (1.0 / i);
19         if(i % 40 == 0) a[i/40] = s;
20     }
21     scanf("%d", &t);
22     while(t--)
23     {
24         scanf("%d", &n);
25         int x = n / 40;
26         s = a[x];
27         for(int i = 40 * x + 1; i <= n; i++) s += (1.0 / i);
28         printf("Case %d: %.10lf
", ca++, s);
29     }
30     return 0;
31 }

【调和级数 && 欧拉常数】 Harmonic Number

Step1 Problem:

Step2 Ideas:

Step3 code：

Step4 code2：参考博客