题解 AT5404 [ABC166D] 【I hate Factorization】

RBI_GL · 2021-04-02 17:53:09 · 题解

题意

已知 a^5-b^5=x，a,b∈Z，x∈Z^+ ，x≤10^9。

给定 x，求出一组 a,b 的值。

思路

直接枚举肯定超时，所以可以考虑缩小枚举范围。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a = 1;
    while(1) {
        a++;
        if (a * a * a * a * a - (a - 1) * (a - 1) * (a - 1) * (a - 1) * (a - 1) > 1e9) {
            cout << a << endl;
            return 0;
        }
    }
    return 0;
}

通过以上程序可以得出 a,b 的枚举上下界为 ±120。

然后枚举即可。得到一组解就结束。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long //注意五次方有可能超过 int
int x;
int qp(int b, int p) { //快速幂
    int ans = 1, base = b;
    while(p > 0) {
        if (p % 2 == 1) ans *= base;
        base *= base;
        p >>= 1;
    }
    return ans;
}
signed main() {
    cin >> x;
    for(int i = -120; i <= 120; ++i) {
        for(int j = -120; j <= 120; ++j) {
            if (qp(i, 5) - qp(j, 5) == x) {
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }
    return 0;
}