题意：求
f
(
n
)
=
1
/
1
+
1
/
2
+
1
/
3
+
1
/
4
…
1
/
n
(
1
≤
n
≤
1
0
8
)
精
确
到
1
0
−
8
f(n)=1/1+1/2+1/3+1/4…1/n (1 ≤ n ≤ 10^8)精确到10^{-8}
f
(
n
)
=
1
/
1
+
1
/
2
+
1
/
3
+
1
/
4
…
1
/
n
(
1
≤
n
≤
1
0
8
)
精
确
到
1
0
−
8
解法1：
调和级数到现在还没有完全正确的公式，但是有个近似的公式：
f
(
n
)
=
l
n
(
n
)
+
C
+
1
/
(
2
∗
n
)
f(n)=ln(n)+C+1/(2*n)
f
(
n
)
=
l
n
(
n
)
+
C
+
1
/
(
2
∗
n
)
n越大越精准，c是欧拉常数
那么我们在n小的时候暴力求，当n很大的时候直接带公式
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double r=0.57721566490153286060651209; //欧拉常数
double a[10000];
int main()
{
a[1]=1;
for (int i=2;i<10000;i++)
{
a[i]=a[i-1]+1.0/i;
}
int n;
cin>>n;
for (int kase=1;kase<=n;kase++)
{
int n;
cin>>n;
if (n<10000)
{
printf("Case %d: %.10lf\n",kase,a[n]);
}
else
{
double a=log(n)+r+1.0/(2*n);
//double a=log(n+1)+r;
printf("Case %d: %.10lf\n",kase,a);
}
}
return 0;
}
解法2：
如果1e8全都记录一定会MLE,我们可以每40个数记录一个数据：分别记录
1
/
40
，
1
/
80
，
1
/
120…1
/
1
0
8
1/40，1/80，1/120…1/10^8
1
/
4
0
，
1
/
8
0
，
1
/
1
2
0
.
.
.
1
/
1
0
8
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 2500001;
double a[maxn] = {0.0, 1.0};
int main()
{
int t, n, ca = 1;
double s = 1.0;
for(int i = 2; i < 100000001; i++)
{
s += (1.0 / i);
if(i % 40 == 0) a[i/40] = s;
}
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
int x = n / 40;
s = a[x];
for(int i = 40 * x + 1; i <= n; i++) s += (1.0 / i);
printf("Case %d: %.10lf\n", ca++, s);
}
return 0;
}