LightOJ - 1234 Harmonic Number（调和级数，分块打表）

链接：LightOJ - 1234 Harmonic Number

题意：

给出$T(\le 10000)$个$n(1\le n\le 10^8)$，求调和级数$H(n)=\sum _{k=1}^n\frac{1}{k}$（精确到$10^{?8}$）

分析：

一共要求$T(\le 10000)$个调和级数，每次都求一遍肯定会超时($O(T?n)$)，考虑打表求一遍把所有答案存起来，但是$n$有$10^8$，会爆内存($O(n)$)。

但是我们可以折中一下，分块打表，例如以50为一个块，仅存储$H(50),H(100),H(150)...$，这样就把空间复杂度降到了$O(n/50)$，查询的时候先查表，然后最多只需要再算49个就行了，时间复杂度降到$O(50?T)$

以下代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1e8+50;
double f[maxn/50];
void init()
{
    double sum=0;f[0]=0;for(int i=1;i<=maxn;i++){
    sum+=1.0/i;if(i%50==0)f[i/50]=sum;}
}
int n,m;
double ans=0;
int main()
{
    init();int T,kase=0;scanf("%d",&T);while(T--){
    scanf("%d",&n);m=n/50;ans=f[m];for(int i=m*50+1;i<=n;i++)ans+=1.0/i;printf("Case %d: %.10f\n",++kase,ans);}return 0;
}