Zenn
👌

ABC 166 | D - I hate Factorization

2020/11/04に公開
競プロ
微分
tech

問題

https://atcoder.jp/contests/abc166/tasks/abc166_d

考えたこと

AとBは整数の組なのでA^5-B^5 = XでAとBを全探索できればいいが、Xが1 \leq X \leq 10^9でありそのままではTLEしてしまうのでAとBの探索範囲を狭められないか考える。

1 \leq Xで整数なのでB < Aである。
また、y=x^5のグラフを考えるとA, B, Xの関係は以下のグラフのようになる。

AとBも整数なのでXの値が10^9を超えたら解は存在しない。
Xが一番小さいのはB=A-1のときなので、差が10^9を超えるのはA>0のときはが120^5 - 119^5 = 1019663401のときである。
Aが負のときも(-119)^5 - (-120)^5 = 1019663401のときである。
よってAもBもそれぞれ-120 \leq A, B \leq 120まで全探索すれば答えを求める事ができる。

コード

実装時のTips

  • 厳密に120でなくても間に合うので200にしている
#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll x;
  cin >> x;
  for (ll a = -200; a <= 200; a++) {
    for (ll b = -200; b <= 200; b++) {
      if (pow(a, 5) - pow(b, 5) == x) {
        cout << a << " " << b << endl;
        return 0;
      }
    }
  }
}

参考

Discussion