問題概要
正整数 $X, Y, A, B$ がある．ここで，次の 2 種類の操作を考える．
- $X \leftarrow XA$
- $X \leftarrow X + B$
$X < Y$ な状態を保ったまま操作できる回数の最大値を求めよ．
制約
- $1 \leq X < Y \leq 10^{ 18 }$
- $2 \leq A \leq 10^9$
- $1 \leq B \leq 10^9$
解法
操作を施していく過程では，次にどちらの操作をするかを選ぶことができます．直感的には，操作後の $X$ が大きくならない方の操作を選ぶのがよいように見えます．実際，$A$ 倍するにせよ $B$ を足すにせよ，元々の $X$ が小さ方が操作後の $X$ が小さくなり，すなわち，$Y$ に達するまでの猶予が大きくなります．
さて，$A$ 倍にする操作というのは，$X$ に $XA - X$ を足す操作と言い換えることができます．つまり，操作後の $X$ の値の大小は，$XA - X$ と $B$ の大小を比較することで求めることができます．また，倍にする操作というのは $X$ を指数的に大きくするので，比較的すぐに $XA - X > B$ となります（もちろん，一度この状態になると覆りません）．そして，$A$ 倍する操作は $O( \log Y )$ 回しか行なえません．
よって操作列の全容は，
- $O( \log Y )$ 回の $A$ 倍操作
- その後，可能な限り $B$ を足す
という構成にするのが最適となります．ステップ 1. については，$( \log Y )$ 回しか行えないことから一回ずつ愚直に処理しても問題ありません．ステップ 2. は最悪時に $\Theta( Y )$ 回操作できてしまうので工夫する必要がありますが，操作回数は $\frac{ ( Y - 1 ) - X } B$ であるので，$O( 1 )$ 時間で計算できます．
結局，全体では $O( \log Y )$ 時間でシミュレートでき，答えが求まります．
コード
main = do [ x, y, a, b ] <- readIntegers print $ solve x y a b solve x y a b | diff_a <= b && x * a < y = 1 + solve ( x * a ) y a b | otherwise = ( ( y - 1 ) - x ) `div` b where diff_a = x * a - x;
