👌

ABC 166 | D - I hate Factorization

2020/11/04に公開

問題

考えたこと

$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;
      }
    }
  }
}

ABC 166 | D - I hate Factorization

問題

考えたこと

コード

参考

Discussion