Harmonic Number LightOJ - 1234

题意：

给你一个调和级数。
$f(n)=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{n}$
要求你求出来。n到达1e8

思路1：

1. 假如直接暴力的话，时间肯定允许，但是内存肯定MLE。
2. 所以可以分段进行打表。

AC1

#include <iostream>
#include <cstdio>
#define For(i,x,y) for(int i=(x); i<=(y); i++)
#define fori(i,x,y) for(int i=(x); i<(y); i++)
using namespace std;
const int N = 1e8+10;
const int maxn = 1e6+10;
double ha[maxn];
void table(){double res = 0;fori(i,1,N){res += 1.0/i;if(i%100==0) ha[i/100] = res;}
}
int main()
{//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);table();int tt, kase = 0; scanf("%d", &tt);while(tt--){double ans = 0;int n; scanf("%d", &n);int st = n/100;ans = ha[st];For(i,st*100+1,n){ans += 1.0/i;}printf("Case %d: %.8f\n", ++kase, ans);}return 0;
}

思路2：

1. 欧拉爷爷，提出了一个解法。提供了一个欧拉常数
2. C = 。。。。111
3. $f(n)=c+ln(n)+\frac{1}{2n}$

AC2

在这里插入代码片