本番中は勘で解いた。
問題リンク
問題概要
1以上\(10^9\)以下の整数Xが与えられる。
整数A,Bの組で\(A^5-B^5=X\)を満たすものを1つ示せ。
ただし、答えとなる(A,B)が存在することは保証されている。
解法
\(A \neq B\)としてよい。
因数分解すると\(A^5-B^5 = (A-B)(A^4+A^3B+A^2B^2+AB^3+B^4)\)である。
\(A^4, A^2B^2, B^4\)は常に正となることに注意する。
この時\(A^3B+AB^3 = AB(A^2+B^2)\)の絶対値は
\(|A| < |B|\)の時\(|B^2(A^2+B^2)| = A^2B^2+B^4\)より小さく、
\(|B| > |A|\)の時\(|A^2(A^2+B^2)| = A^4+A^2B^2\)より小さくなる。
したがって\(|A^5-B^5| \geqq |A-B||A^4| \geqq A^4\)もしくは\(|A^5-B^5| \geqq B^4\)が成り立つ。
したがって、\(|A|^4, |B|^4 > 10^9 \geqq X\)となる解は無いので
\(|A|^4, |B|^4 \leqq 10^9\)となる範囲を全探索すればよい。
\( |A|, |B| \leqq 10^{9/4} \fallingdotseq 177.8\)で十分。
提出
https://atcoder.jp/contests/abc166/submissions/12733812
https://atcoder.jp/contests/abc166/submissions/12760600(こっちのほうが簡潔)
感想
めちゃくちゃびびった。
