1 /* 2  LightOJ1234 Harmonic Number  3  http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1234 4  打表 分块 5  由于只有加法运算，1e8时间是可以承受的。 6  然而空间无法承受，于是以50个单位为一块进行分块。 7  */ 8 #include <cstdio> 9 #include <algorithm>10 #include <cstring>11 #include <cmath>12 #include <vector>13 #include <queue>14 #include <iostream>15 #include <map>16 #include <set>17 //#define test18 using namespace std;19 #ifdef old20 const int Nmax=1e6+7;21 double f[Nmax];22 #endif23 const int Nmax=1e8+5;24 const double eps=1e-9; 25 double f[Nmax/50+5];26 //double get_f(int n)27 //{28     //if(n<Nmax)29         //return f[n];30     //return 1.0/n+get_f(n-1);31 //}32 #ifdef old33 map<int ,double> mp;34 map<int ,double>::iterator it;35 double get_f(int n)36 {37     if(n<Nmax)38         return f[n];39     it=mp.find(n);40     if(it!=mp.end())41         return mp[n];42     it=mp.upper_bound(n); 43     if(it!=mp.begin())44         it--;45     //printf("it->n:%d\n,it->first);46     double ans=it->second;47     for(int i=it->first+1;i<=n;i++)48     {49         ans+=1.0/i;50     }51     mp[n]=ans;52     return ans;53 }54 #endif55 int main()56 {57     #ifdef test58     #endif59     //freopen("loj1234.in","r",stdin);60     //freopen("tras.out","w",stdout);61 #ifdef old62     f[1]=1.0;63     for(int i=2;i<Nmax;i++)64        f[i]=f[i-1]+1.0/i;65 #endif66     //for(int i=1;i<=15;i++)67         //printf("%lf\n",f[i]);68 #ifdef old69     mp[Nmax-1]=f[Nmax-1]; 70 #endif71     double tmp=0.0;72     for(int i=1;i<=1e8;i++)73     {74         tmp+=1.0/i;75         if(i%50==0)76             f[i/50]=tmp;77     }78     int n;79     int t;80     scanf("%d",&t);81     t=0;82     while(scanf("%d",&n)==1)83     {84         t++;85         printf("Case %d: ",t);86         double ans=0.0;87         ans=f[n/50];88         for(int i=n/50*50+1;i<=n;i++)89             ans+=1.0/i;90         printf("%.8lf\n",ans+eps);91 #ifdef old92         printf("%.8lf\n",get_f(n)+eps);93 #endif94 95     }96     return 0;97 }