問題概要
正整数 $X$ が与えられる．$A^5 - B^5 = X$ となる整数 $A, B$ の組を一つ示せ．なお，解が存在するような $X$ のみが与えられる．
制約
- $1 \leq X \leq 10^9$
解法
本題に入る前に，$f( x ) = x^5$ という関数の形について少し考えておきます（問題文中の式に含まれている項なので）．すぐに分かることとして，$x$ の指数が $5$ と大きめであるため，それなりに速く発散します．また，$-f( x ) = f( -x )$ です．
以上を踏まえて問題文で与えられた式（の左辺）について考えていきます．$A, -B$ の符号で（対称な式をまとめつつ）分類すると，
- $A^5$ も $-B^5$ も正
- $A^5$ と $-B^5$ の片方が正，他方が負
- $A^5$ も $-B^5$ も負
の 3 パターンになります．この内，最初のパターンは発散が速い値同士の和なので速く発散します．$100^5 = 10^{10}$ なので，このケースでは $A$ の指数が $100$ もあれば十分です．また，最後のパターンは，和が負になるものの $X$ は正であるため不適です．
2 番目のパターンではどうなるでしょうか．この場合，発散が速いものと発散が速いものの差をとっていますが，差の方も発散が速いかどうかはパッと見では分かりません*1．差をできるだけ小さくするような形として，$y^5 - ( y - 1 )^5$ という形を考えてみます（$( y - 1 )$ の項を $( y - 2 ), ( y - 3 ), \dots$ と小さくしていくと差は大きくなっていくので，差が小さい場合を考えたいならこの形になります）．適当な値を入れて計算してみます．$100^5 - 99^5 = 490{,}099{,}501$ となり……って，足りてませんね．$200^5 - 199^5 = 7{,}920{,}399{,}001$ となり $X$ の最大値を超えてます．1 項目が $200$ ではなくもっと小さい値だったとしても，2 項目が小さくなると差は大きくなり，$-200$ あたりまで行く頃には十分に $X$ を超えています．よって，$-200$ から $200$ ぐらいの範囲で $A, B$ を探せばよいことが分かります*2．また，この範囲で探せば，先程の 1 番目のパターンもカバーできています．
さて，上記の範囲で $A, B$ を全探索すれば問題を解くことができると分かりました．この全探索の計算時間は，入力によらず決まった範囲を探索するので $O( 1 )$ 時間です．
コード (Haskell)
readInt = readLn :: IO Int main = do x <- readInt uncurry ( printf "%d %d\n" ) $ head $ do i <- [ -200 .. 200 ] j <- [ -200 .. 200 ] guard $ i ^ 5 - j ^ 5 == x return ( i, j )
