自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:40:18，当前版本为作者最后更新于2022-10-07 20:43:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

注：本题解中的做法为出题人原做法，并不代表最优。

考虑对于 $\forall k$，有多少 $n$ 使得 $f(n)=k$。

因为 $f(n)$ 为整数，且 $(k+\frac{1}{2})^4$ 不为整数，可知 $k+\frac{1}{2} \le f(n) \le k+\frac{1}{2}$，即 $n$ 有 $(k+\frac{1}{2})^4-(k-\frac{1}{2})^4$ 种取值，化简得 $4k^3+k$。

所以设 $p(t)=\sum_{i=1}^{t} \frac{4i^3+i}{i}$，$q(t)=\sum_{i=1}^{t} 4i^3+i$，其中 $t$ 满足 $q(t) \le n < q(t+1)$，则答案为 $p(t)+\frac{n-q(t)}{t+1}$，复杂度为 $\log$ 级别的，能通过此题。

这里给出计算的代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n;
signed main(){
	cin>>t;
	while(t--){
		cin>>n;
		long double ans=0.0;
		int sum=0,cnt=0;
		while(true){
			cnt++;
			if(sum+4*cnt*cnt*cnt+cnt>n)break;
			ans+=4*cnt*cnt+1;
			sum+=4*cnt*cnt*cnt+cnt;
		}
		ans+=1.0*(n-sum)/cnt;
		cout<<fixed<<setprecision(6)<<ans<<endl;
	}
	return 0;
}