Harmonic Number
Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Submit Status
Description
In mathematics, the nth harmonic number is the sum of the reciprocals of the first n natural numbers:
Hn=1/1+1/2+1/3+1/4…1/n
In this problem, you are given n, you have to find Hn.
Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 108).
Output
For each case, print the case number and the nth harmonic number. Errors less than 10-8 will be ignored.
Sample Input
12
1
2
3
4
5
6
7
8
9
90000000
99999999
100000000
Sample Output
Case 1: 1
Case 2: 1.5
Case 3: 1.8333333333
Case 4: 2.0833333333
Case 5: 2.2833333333
Case 6: 2.450
Case 7: 2.5928571429
Case 8: 2.7178571429
Case 9: 2.8289682540
Case 10: 18.8925358988
Case 11: 18.9978964039
Case 12: 18.9978964139
题意：计算调和级数的前n项和(n<=1e8)。
这题看了好多人的写法都是用公式，看到一个比较好的解法记录一下，^ ^,博客地址为：http://www.cnblogs.com/shentr/p/5296462.html，数据范围有点大，时间限制是3s，如果直接打表的话时间是够的但是1e8的数组肯定MLE了，这里可以考虑每40组记录一个值，输入的数直接除以40就可以得到一个数，最多再进行39次运算就能得到结果了
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<queue> #include<cstring> #include<string> #include<map> #include<set> using namespace std; typedef long long ll; #define for1(i,a) for(int (i)=1;(i)<=(a);(i)++) #define for0(i,a) for(int (i)=0;(i)<(a);(i)++) #define sf scanf #define pf printf #define mem(i,a) memset(i,a,sizeof i) #define pi acos(-1.0) #define eps 1e-10 const int Max=1e8; const int M=Max/40; double s[M+1]={0.0,0.0}; int m,n; int main() { double d=1; for(int i=2;i<=Max;i++)//打表求出1e8的所有值每40个分一个组，时间大概为1s多一点 { d+=(1.0/i); if(!(i@)) s[i/40]=d; } sf("%d",&m); for1(i,m) { sf("%d",&n); int j=n/40; double ans=s[j];//求出n所对应的数组，再继续算剩余的部分即可 for(int k=j*40+1;k<=n;k++) ans+=1.0/k; pf("Case %d: %.10f\n",i,ans); } return 0; }
