自动搬运

查看原文

来自洛谷，原作者为

	Vel_ **

搬运于2025-08-24 21:20:10，当前版本为作者最后更新于2019-01-22 01:10:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Code

Force $O(e^k)$

写一个累加器和一个溢出灯就行。

以后可能会将回归性函数称为器，分类性函数称为灯。

#include<bits/stdc++.h>
using namespace std;

bool excess(double sn,double k){ //溢出灯
	return sn > k;
}

int main(){
	int i=1;
	double sn=0,k;
	cin>>k;
	while(1){ //累加器
		sn += (double)1/(double)(i++);
		if(excess(sn,k)) {cout<<i-1;break;}
	}
	return 0;
}

数论优化 $O(logk)$

https://www.luogu.org/problemnew/solution/P1035

exp(k)是指数调用的复杂度，最高可以优化到log(k)（相当多项式幂），因此最后得到的复杂度为$O(logk)$。

值得指出的$O(logk)$仅仅是理论的，因为最后cout打印的数的宽度已经是O(k)了！

运算虽然可以很快，却会被输出所限制。

#include<bits/stdc++.h>
using namespace std;

bool excess(double sn,double k){
	return sn > k;
}

int main(){
	int i=1;
	double k;
	while(cin>>k){
		cout<<floor(exp(k-0.5772156649) + 0.5)<<endl;
	}
	return 0;
}