P3766 核心密码B 题解

a12a · 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)}。

可以裂项了！

现在要求的：

一道黑题就这么做完了。

实现

• 由于 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';
}