LightOJ – 1234 Harmonic Number

Harmonic Number

(有技巧的打表)

直接打表爆内存,隔50个打表还行.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define ll long long
using namespace std;
const int maxn = 1e8;

double H[2000000];
void getH(){
    int k=0;
    double res=0;
    for(int i=1;i<=maxn;++i){
        res=res+1.0/i;
        if(i%50==0) H[++k]=res;
    }
}

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T, kase = 0;
  getH();
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    double ans=H[n/50];
    int t=(n/50)*50;
    for(int i=1;i<=n%50;++i){
        ans=ans+1.0/(t+i);
    }
    printf("Case %d: %.10lf\n", ++kase,ans);
  }
  return 0;
}