AT5404 题解

wangkangyou · 2022-08-15 15:05:31 · 题解

传送门

简述一下题意：(其实也没什么好简述的了) 给你一个数 x , 试求方程 a^{5} - b^{5}=x 的一组解 a,b。

讲一下我的思路：

暴力枚举即可。此题难在判断枚举范围上。其实我们可以从 x 下手。由于 x 为两个数相减的差，我们可以极端一点，假设两项的底数一定是相邻的，那么我们可以一个个枚举一组组相邻底数的 5 次方的差:

其实我们从以上过程中可以发现，差的绝对值在几乎是在直线增长。终于到了第 119 组的时候我们发现：

差已经大于了10^{9}了。但是还没完，我们统计的是 a,b 为正数且递增的情况，正数的答案虽然有可能是 a,b 为正数且递减的情况下，然而更多可能是存在于 -120 至 0 的范围中。于是我们的枚举范围就变成了从 -120 到 120 这一个区间内。

参考代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
    int sum=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) sum=(sum<<3)+(sum<<1)+(ch^48);
    return sum*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar('0'+x%10);
    return;
}
const int inf=1e10;
const int N=1e6+10;
int qpow (int a, int b){//快速幂，相当于a^b,理解即可
    if (b == 0) return 1;
    if (b == 1) return a;
    int t = qpow (a, b / 2);
    if (b % 2 == 1) return t * t * a;
    return t * t;
}
signed main(){
    int x = read ();
    for (int i = -150; i <= 150; ++ i){
        for (int j = -150; j <= 150; ++ j){
            int a = qpow (i, 5);
            int b = qpow (j, 5);
            if (a - b == x){
                write (i);
                putchar (' ');
                write (j);
                return 0;
            }
        }
    }
    return 0;
}