P1035 级数求和

· · 题解

在算模拟做法（做法1）的时间复杂度时，我想到了一种新的数论做法（做法2），检查了一遍题解发现没有这种做法，于是我写了这篇题解。

1.模拟

这种做法的思路是枚举n从1开始，直到Sn>k结束，只需要一个循环即可实现。

代码：

#include<cstdio>
int main() {
    int k,n=0;
    scanf("%d",&k);
    for(double Sn=0;Sn<=k;++n,Sn+=1.0/n);
    printf("%d",n);
    return 0;
}

空间复杂度O(1)

时间复杂度O(e^{k-\gamma})（求法见做法2）

（如果那个\gamma可以约去的话，应该是O(e^k)，但并不知道可不可以约去）

2.数论（调和级数）

关于调和级数的姿势，点这里。

已知Sn=1+1/2+1/3+...+1/n=\sum_{k=1}^{n}\frac{1}{k}。

明显地，Sn为第n个调和数。

欧拉推导过求调和级数有限多项和的表达式为\sum_{k=1}^{n}\frac{1}{k}=\ln(n+1)+\gamma，我们拿过来用即可。（\gamma约等于0.5772156649）

我们需要满足Sn>k，即满足\ln(n+1)+\gamma>k，化简得n>e^{k-\gamma}-1。

我们只需求满足上式的最小的n，所以n=e^{k-\gamma}+0.5（四舍五入），即模拟做法的时间复杂度为O(e^{k-\gamma})。

关于\gamma（欧拉-马歇罗尼常数）的姿势，点这里。

代码：

#include<cstdio>
#include<cmath>
const double gamma=0.5772156649;
int main() {
    int k,n;
    scanf("%d",&k);
    n=exp(k-gamma)+0.5;
    printf("%d",n);
    return 0;
}

空间复杂度O(1)

时间复杂度O(???)

（因为不知道math.h头文件中的exp函数的时间复杂度，所以不知道时间复杂度）

未解决的问题

1.时间复杂度O(e^{k-\gamma})中的\gamma可不可以约去？

2.math.h头文件中的exp函数的时间复杂度为多少？

3.有dalao说\gamma是极限意义下的，不能直接k-\gamma是什么意思？

最后，

欢迎各位留言吐槽。

欢迎dalao答疑。

欢迎神犇纠错。