D - 繰り返し (Repetition) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100

問題文

正の整数 X, N が与えられる.

最初,黒板に整数 X が書かれている.

JOI 君は,以下の操作を繰り返し行う.

操作: 今,黒板に書かれている数を x とする.x3 で割った余りを計算し,r とする.r の値に応じて,黒板に書かれている数を以下のように書き換える.

  • r=0 のとき,黒板に書かれている数を,x1 を足した数に書き換える.
  • r=1 のとき,黒板に書かれている数を,x2 を掛けた数に書き換える.
  • r=2 のとき,黒板に書かれている数を,x3 を掛けた数に書き換える.

黒板に書かれている数が N 以上になるまでに必要な操作の回数を求めよ.

制約

  • 1 \leqq X < N \leqq 100\,000
  • 入力される値はすべて整数である.

入力

入力は以下の形式で与えられる.

X
N

出力

黒板に書かれている数が N 以上になるまでに必要な操作の回数を出力せよ.

答え以外は何も出力しないこと.(入力を促す文章なども出力しないこと.)

解答形式については,練習問題やその解答例 を参考にしても良い.


入力例 1

2
40

出力例 1

4

最初,黒板に書かれている数は 2 である.

1 回目の操作では,操作の始めに黒板に書かれている数 x2 である.x3 で割った余り r2 であるため,黒板に書かれている数を,x=23 を掛けた数である 6 に書き換える.

2 回目の操作では,操作の始めに黒板に書かれている数 x6 である.x3 で割った余り r0 であるため,黒板に書かれている数を,x=61 を足した数である 7 に書き換える.

3 回目の操作では,操作の始めに黒板に書かれている数 x7 である.x3 で割った余り r1 であるため,黒板に書かれている数を,x=72 を掛けた数である 14 に書き換える.

4 回目の操作では,操作の始めに黒板に書かれている数 x14 である.x3 で割った余り r2 であるため,黒板に書かれている数を,x=143 を掛けた数である 42 に書き換える.

4 回操作したとき初めて黒板に書かれている数が 40 以上になるため,4 を出力する.


入力例 2

3
4

出力例 2

1

入力例 3

20
62

出力例 3

3

入力例 4

1
100000

出力例 4

19