P8574官方题解

FWT__FFT · 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;
}