星之影-垃圾推式子
简而言之，本题题意为求：
\[\sum_{x=1}^n\frac{1}{\lfloor\sqrt[4]x+\frac{1}{2}\rfloor} \]观察这个式子，我们会发现， \(\sqrt[4]x\) 增长非常慢，于是可以采用类似于数论分块的思想
很明显， \({\lfloor\sqrt[4]x+\frac{1}{2}\rfloor}\) 的值是非严格单调递增的，且取\(1,2,3,4,……\)
下面我们来思考这个式子的值为 \(m\) 的时候， \(x\) 的取值范围，容易发现， \(x\) 最小可以是当 \(\sqrt[4]x+\frac{1}{2}=m\) ,也即 \(x=(\frac{2m-1}{2})^4\) 由于 \(m\) 是整数， \(x\) 是整数，可以知道 \(x\) 最大取到 \(x=(\frac{2m+1}{2})^4-1\) ,这里一共有取值总数：
\[(\frac{2m+1}{2})^4-1-(\frac{2m-1}{2})^4+1=4m^3+m \]故对于一个足够大的 \(n\) ,当 \({\lfloor\sqrt[4]x+\frac{1}{2}\rfloor}=m\) 时，\(m\)的总贡献为： \(4m^2+1\) ,所以说，我们设 \(a\) 是对于 \(n\) 来说，满足 \(\sum_{k=1}^a(4k^3+k)\le n\) 的最大的 \(a\) ,这意味着我们可以直接对 \(1\sim a\) 的贡献进行求和，写成式子即这部分贡献为：
\[\sum_{k=1}^a\frac{1}{k}·(4k^3+k)=4\sum_{k=1}^ak^2+\sum_{k=1}^a1=\frac{2a(a+1)(2a+1)+3a}{3} \]那么对于答案来说，剩下的部分即为值为 \(a+1\) 的部分，这个部分的总数量即为 \(1\sim n\) 的数量减去 \(1\sim a\) 中每个数出现的次数，写成式子即为：
\[n-\sum_{m=1}^a(4m^3+m)=n-4\sum_{m=1}^am^3-\frac{a(a+1)}{2}=n-a^2(a+1)^2-\frac{a(a+1)}{2} \]其总贡献为：
\[\frac{1}{a+1}\left(n-a^2(a+1)^2-\frac{a(a+1)}{2}\right) \]故，此时我们便可以计算出答案：
\[\frac{2a(a+1)(2a+1)+3a}{3}+\frac{1}{a+1}\left(n-a^2(a+1)^2-\frac{a(a+1)}{2}\right) \]我们发现，现在我们的问题就是如何求出 \(a\) 的值
笔者在考场上，暂时没有想出，于是由于 \(a\) 的值具有单调性于是二分答案做的，此种做法已经可以通过本题，但本题还有\(O(1)\)做法
我们想想，对于 \(a\) 的定义是什么，很明显，是满足 \(\sum_{k=1}^a(4k^3+k)\le n\) 的最大的 \(a\) ，化简这个和式，有：
\[a^2(a+1)^2+\frac{a(a+1)}{2}\le n \]我们使用换元法求解这个方程，很明显，令 \(t=a(a+1)\) ,则原方程化为： \(t^2+\frac{t}{2}\le n\) ,由于\(t\)肯定是一个正数，可以解得 \(0<t\le \frac{\sqrt{1+16n}-1}{4}\) ,带回 \(a\) ,可以解得 \(0<a\le \frac{\sqrt[4]{1+16n}-1}{2}\) ,根据 \(a\) 的定义，有 \(a=\left\lfloor\frac{\sqrt[4]{1+16n}-1}{2}\right\rfloor\) 也即 \(a+1=\left\lfloor\frac{\sqrt[4]{1+16n}+1}{2}\right\rfloor\)
所以说，我们可以 \(O(1)\) 的计算每一次的答案，不需要任何的预处理，这道题的答案写成最终形式就是：
\[\sum_{i=1}^n\frac{1}{\lfloor\sqrt[4]x+\frac{1}{2}\rfloor}=\frac{2a(a+1)(2a+1)+3a}{3}+\frac{1}{a+1}\left(n-a^2(a+1)^2-\frac{a(a+1)}{2}\right) \]其中 \(a=\left\lfloor\frac{\sqrt[4]{1+16n}-1}{2}\right\rfloor\)
那么程序也就不难实现了：
#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long
int n,m,t;
int get(int x){//求1/1~1/n的所有项的和
return (2*x*(x+1)*(x*2+1)+3*x)/3;
}
int count(int x){
return x*x*(x+1)*(x+1)+x*(x+1)/2;
}
int find(int n){//寻找第n个数是属于a的哪一个元素
return (sqrt(sqrt(1.0+16.0*n))+1)/2;
}
double solve(int t){
double ans=0;
int now=find(t);
// printf("%lld \n",now);
ans+=get(now-1);
ans+=1.0*(t-count(now-1))/now;
return ans;
}
typedef long long ll;
char buf_ans[114];
ll next_n(double last_ans=0,ll get_n=0){
//last_ans<n<=1e18
sprintf(buf_ans,"%.6f",last_ans);
for(ll i=0,x=0;;i++){
if(buf_ans[i]=='.')return get_n^x;
if(i&1)x*=10;
else x=x*10+(buf_ans[i]^48);
}
}
signed main(){
scanf("%lld",&t);
double lst=0;
while(t--){
int x;
scanf("%lld",&x);
x=next_n(lst,x);
printf("%.6f\n",lst=solve(x));
}
}
注：
- 程序中代码是求的a+1
- \(\sum_{i=0}^ni^2=\frac{n(n+1)(2n+1)}{6}\)
- \(\sum_{i=0}^{n}i^3=\frac{n^2(n+1)^2}{4}\)
- 前面两个式子可以试着推一推
练习题：
求：
这个甚至比上一个更加简单，只需要套一下就行
标签：lfloor,frac,int,sum,ans,sqrt,星之影,数学,简单 From： https://www.cnblogs.com/oierpyt/p/16940059.html