Harmonic Number LightOJ - 1234

题意：

给你一个调和级数。
f ( n ) = 1 + 1 2 + 1 3 + 1 4 + 1 5 + . . . + 1 n f(n)=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{n} f(n)=1+21​+31​+41​+51​+...+n1​
要求你求出来。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 + l n ( n ) + 1 2 n f(n)=c+ln(n)+\frac{1}{2n} f(n)=c+ln(n)+2n1​

AC2

在这里插入代码片