Mr Loser

ABC 166 D I hate Factorization

2020-05-03 22:26:56


刚开始看的时候被吓懵了...然后推柿子推了半天没想出来...最后半小时才开始写...wtcl

我们不妨先来分析一下如下柿子的意义:

$$A^5-B^5=X$$

不难得出,我们要求的是两个完全五次方数(这个说法可能不太学术。。能理解意思就好),使它们的差是 $X$。

我们不妨先打完全五次方数的表 $A_n=n^5$。实测当 $n=1000$ 时, $n^5-(n-1)^5$ 远大于 $10^9$,于是我们打这个范围( $n\in [-1000,1000]$)足够了。

后面的事情就顺理成章了。遍历 $A_i$,二分查找第一个大于等于 $A_i+X$ 的数,然后判断输出即可。

由于这个表中的数的五次方跟是连续的,所以我们不必再用精度低的一批的 pow。具体的看代码:

#include<cstdio>
#include<algorithm>
#define int long long
int a[20001],x;
signed main(){
    for(int i=-1000;i<=1000;i++)a[i+1000]=1ll*i*i*i*i*i;//i+1000将遇到的负数变为自然数
    scanf("%lld",&x);
    for(int i=0;i<=2000;i++){
        int k=std::lower_bound(a+i+1,a+2000,a[i]+x)-a;
        if(a[k]==a[i]+x)return printf("%lld %lld\n",k-1000,i-1000),0;//表中的位置减去1000即为底数
    }
}