問題概要
正整数 $N$ が与えられる．$3^A + 5^B = N$ を満たす整数の組 $( A, B )$ を一つ見つけよ．存在しない場合は代わりに $-1$ を出力せよ．
制約
- $1 \leq N \leq 10^{ 18 }$
解法
$A, B$ が指数の肩に乗っているため，$A, B$ を大きくしていくと $3^A, 5^B$ は指数的に大きくなります．また，一旦 $3^A > N$ や $5^B > N$ になるとその先に解はありません．つまり，$A, B$ はそれぞれ $O( \log N )$ 通りぐらいしか候補がありません．この範囲であれば組合せを全通り試してしまえる程度の個数なので，そのようにします．計算量としては，試すべき整数の対が $O( ( \log N )^2 )$ 個あるので，$O( ( \log N )^2 )$ 時間になります．
コード
main = do n <- readInteger let res = do a :: Int <- takeWhile ( \a -> 3 ^ a <= n ) [ 1 .. ] b :: Int <- takeWhile ( \b -> 5 ^ b <= n ) [ 1 .. ] guard $ 3 ^ a + 5 ^ b == n return ( a, b ) if null res then print (-1) else uncurry ( printf "%d %d\n" ) $ head res
