ABC 166
Table of Contents
https://atcoder.jp/contests/abc166
A. A?C
https://atcoder.jp/contests/abc166/tasks/abc166_a
B. Trick or Treat
https://atcoder.jp/contests/abc166/tasks/abc166_b
C. Peaks
https://atcoder.jp/contests/abc166/tasks/abc166_c
D. I hate Factorization
https://atcoder.jp/contests/abc166/tasks/abc166_d
自力 AC したが、正当性が証明できなかったので嘘解法だったかもしれない。
$A^5 - B^5 = (A-B)(A^4 + A^3B + A^2B^2 + AB^3 + B^4)$ という因数分解できるので $A-B$ の値を $[1, \sqrt{X}]$ くらいの範囲で固定して $A$ の値を $A^4 \leq X/(A-B)$ くらいの範囲で収まる $A$ で検索すればいいかなという感じで実装した。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll X;
cin >> X;
// A^5 - B^5 = (A-B)(A^4 + A^3*B + A^2*B^2 + A*B^3 + B^4)
for (ll d = 1; d * d <= X; d++) {
if (X % d != 0) continue;
ll t = X / d;
for (ll a = 0; a * a * a * a <= t; a++) {
ll b = a - d;
if (a * a * a * a * a - b * b * b * b * b == X) {
cout << a << ' ' << b << endl;
return;
}
}
}
}
正しい解法
$A, B$ の差が大きいと $X$ の値がすぐに大きくなる。一方で差が小さいと $A$ の値が大きくできる。 $A$ をなるべく大きくするためには $B$ の値をなるべく $A$ に近づけたほうが良い。$1 \leq X \leq 10^9$ より $A \neq B$ であるから $B = A-1$ のとき、$A$ の値をなるべく大きくすることができる。
一方で $120^5 - (120-1)^5 > 10^9$, $-120^5 - (-120-1)^5 > 10^9$ となるので $A$ の動かせる範囲はせいぜい $[-120, 120]$ 程度である。 $B$ の値も同様。よってこれらの範囲で $A, B$ を動かして全探索すればよい。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll X;
cin >> X;
rep2(a, -120, 121) rep2(b, -120, 121) {
if (a * a * a * a * a - b * b * b * b * b == X) {
cout << a << ' ' << b << endl;
return;
}
}
}
E. This Message Will Self-Destruct in 5s
https://atcoder.jp/contests/abc166/tasks/abc166_e