洛谷5515 [MtOI2019]灵梦的计算器

题意

给出 $N,A,B$ ，求 $N_0$ 的最值，使得 $\lfloor N^A+N^B \rfloor = \lfloor {N_0}^A+{N_0}^B \rfloor$ 。有 $T$ 组数据，答案为每组数据中 $\max N_0 - \min N_0$ 的和。

输入方式请看原题。

$4\le N\le 5 \ , \ 5\le A,B\le 10 \ , \ T\le 5\times 10^6$ 。

题解

代码中的读入都被省略掉了，请去原题找。

容易想到朴素的二分，可以得到 $65$ 分：

#include<bits/stdc++.h>
#define eps 1e-7

using namespace std;

signed main()
{
    int t; scanf("%d",&t);
    Mker::init();
    double n,a,b,ans=0;
    while (t--)
    {
        Mker::read(n,a,b);
        int cur=pow(n,a)+pow(n,b);
        double l=4,r=n,res;
        while (r-l>eps)
        {
            double mid=(l+r)/2;
            if ((int)(pow(mid,a)+pow(mid,b))==cur) r=mid;
            else l=mid;
        }
        res=l; l=n; r=5;
        while (r-l>eps)
        {
            double mid=(l+r)/2;
            if ((int)(pow(mid,a)+pow(mid,b))==cur) l=mid;
            else r=mid;
        }
        ans+=l-res;
    }
    return !printf("%f",ans);
}

然后wzx大佬提醒我可以用牛顿迭代

令 $f(x)=x^A+x^B-(N^A+N^B)$ ，答案即求 $f(x)=0$ ，典型的牛顿迭代。我还对其化了简，使得可以少计算几次 pow() 。

于是我肝了 $30min$ ，很开心的多了 $5$ 分，有 $70$ 了：

#pragma GCC optimize("fast-math")
#include<bits/stdc++.h>
#define eps 1e-5

using namespace std;

double n,a,b,ans;

inline double work(int cur)
{
    double x=4;
    for (;;)
    {
        double _x=pow(x,a-b);
        double nx=((a-1)*_x*x+(b-1)*x+cur/pow(x,b-1))/(a*_x+b);
        if (abs(x-nx)<eps) break;
        x=nx;
    }
    return x;
}

signed main()
{
    int t; scanf("%d",&t);
    Mker::init();
    while (t--)
    {
        Mker::read(n,a,b);
        if (a<b) swap(a,b);
        int cur=pow(n,a)+pow(n,b);
        double res=work(cur);
        ans+=work(cur+1)-res;
    }
    return !printf("%f",ans);
}

赛后去看题解，发现有个评论

但我只迭代一次连样例都过不去，怀疑是化简以后精度出了问题，于是我不化简的写了一份只迭代一次的：

#pragma GCC optimize("fast-math")
#include<bits/stdc++.h>
#define eps 1e-5

using namespace std;

double n,a,b,ans;

inline double work(int cur)
{
    double f=pow(n,a)+pow(n,b)-cur;
    double _f=a*pow(n,a-1)+b*pow(n,b-1);
    return n-f/_f;
}

signed main()
{
    int t; scanf("%d",&t);
    Mker::init();
    while (t--)
    {
        Mker::read(n,a,b);
        int cur=pow(n,a)+pow(n,b);
        double res=work(cur);
        ans+=work(cur+1)-res;
    }
    return !printf("%f",ans);
}

得了 $80$ 分。

然后我又看到这个讨论，就直接用化简后的结论过了。

#pragma GCC optimize("fast-math")
#include<bits/stdc++.h>
#define eps 1e-5

using namespace std;

double n,a,b,ans;

signed main()
{
    int t; scanf("%d",&t);
    Mker::init();
    while (t--)
    {
        Mker::read(n,a,b);
        ans+=n/(a*pow(n,a)+b*pow(n,b));
    }
    return !printf("%f",ans);
}