自动搬运

查看原文

来自洛谷，原作者为

	a12a 逸一时，误一世，逸久逸久罢己龄。

搬运于2025-08-24 21:52:29，当前版本为作者最后更新于2024-02-27 21:13:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

抗议积分暴政，世界属于小奥！

前置芝士

• 分数裂项

• 平方差公式

$k \ge 3$ 时

很显然，即使一个一个枚举数据量也只有 $10^6$ 的数量级。直接将 $n$ 个询问排序后离线处理即可。

$k=2$ 时

题目让我们求和的是一坨分数，结合小奥不难想到分数裂项。

但是 $\frac{1}{x^2}$ 显然无法裂项，这可怎么办呢？

注意到误差在 $2\times 10^{-14}$ 内即可，而 $10^7$ 的数据量可以直接枚举。

所以，我们对于 $> 10^7$ 的询问只需要求一个大差不差的近似值。结合七下的平方差公式，不难想到将 $\frac{1}{x^2}$ 取成 $\frac{1}{x^2-1}=\frac{1}{(x+1)(x-1)}$。

可以裂项了！

$$\frac{1}{(x+1)(x-1)}=\frac{1}{2}(\frac{1}{x-1}-\frac{1}{x+1}) $$

现在要求的：

$$\begin{aligned} \sum_{x=10^7+1}^{\sqrt q_i} \frac{1}{2} (\frac{1}{x-1}-\frac{1}{x+1}) &=\frac{1}{10^7}-\frac{1}{10^7+2}+\frac{1}{10^7+1}-\frac{1}{10^7+3}+\frac{1}{10^7+2}-\frac{1}{10^7+4}+\frac{1}{10^7+3}-\frac{1}{10^7+5}+......+\frac{1}{q_i-1}-\frac{1}{q_i+1} \\ &= \frac{1}{10^7}+\frac{1}{10^7+1}-\frac{1}{q_i-1}-\frac{1}{q_i} \end{aligned} $$

一道黑题就这么做完了。

实现

• 由于 $2\times 10^{-14}$ 的误差，需要用到 long double 和 sqrtl() 函数。

• 快速幂最好用 __int128，以免出现一些奇怪的精度错误。

• 由于 $n \le 10^{18}$，需要开 long long。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
	int x,id;
}q[100010];
int T;
long double ans[100010];
bool cmp(node a,node b)
{
	return a.x<b.x;
}
__int128 qpw(__int128 a,int b)
{
	__int128 sum=1;
	for(;b;b/=2,a*=a)
		if(b%2==1)
			sum*=a;
	return sum;
}
void f(int x)
{
	__int128 t=2,r=qpw(t,x);
	long double sum=0;
	for(int i=1;i<=T;i++)
	{
		while(r<=q[i].x)
		{
			long double tmp=1.0;
			tmp/=r,sum+=tmp,t++,r=qpw(t,x);
		}
		ans[q[i].id]+=sum;
	}
}
signed main()
{
	cin>>T;
	for(int i=1;i<=T;i++)
		cin>>q[i].x,q[i].id=i;
	sort(q+1,q+T+1,cmp);
	for(int i=3;i<=63;i++)
		f(i);
	for(int i=1;i<=T;i++)
	{
		if(q[i].x>1e14)
		{
			int x=sqrtl(q[i].x);
			long double t1=1.0,t2=1.0,t3=1.0,t4=1.0;
			t1/=(long double)(1e7),t2/=(long double)(1e7+1),t3/=(long double)(x),t4/=(long double)(x+1),t1=t1*1.0+t2*1.0-t3*1.0-t4*1.0,t1=t1*1.0/(long double)(2.0),ans[q[i].id]+=t1,q[i].x=1e14;
		}
	}
	f(2);
	for(int i=1;i<=T;i++)
		cout<<setprecision(15)<<fixed<<ans[i]<<'\n';
}