Harmonic Number

题目

图片说明

分析

这题的打表比较有意思，一共有的计算量，这里有3秒的时限，是可以进行几次的的计算的，可是我们没办法开一个的数组来保存每一项的值，所以我们可以每隔50个打一个表，这样我们只需要进行一次的计算，之后次询问，每次我们只需要进行至多50次计算就可以了。

AC代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long ll;
ll T,N;
double f[2000010];
void init(){
    double cur = 0;
    for(ll i = 1;i<=100000000;i++){
        cur += 1.0/i;
        if(i%50 == 0){
            f[i/50] = cur;
        }
    }
}
double fun(){
    double cur = f[N/50];
    for(ll i = N/50*50+1;i<=N;i++){//算N%50的部分
        cur += 1.0/i;
    }
    return cur;
}
int main(){
    init();
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%lld",&N);
        double res = fun();
        printf("Case %d: %.9lf\n",++kase,res);
    }
    return 0;
}