No.141 魔法少女コバ
koba-e964問題文
魔法少女のコバは数を変化させる魔法を覚えました。コバが使える魔法は以下の2種類です:
(1)数$a$に$1$を加えて$a+1$に変える。
(2)数$a$が$0$でない時、$a$をその逆数$1/a$に変える。
数$1$に魔法をかけて次々に変化させていくとき、与えられた数$M/N$にするまでに必要な最小の魔法の回数を出力してください。
もし$1$をどのように変化させても$M/N$が得られない場合は、$-1$を出力してください。
$M$と$N$は互いに素とは限りませんが、互いに素でない場合は、$M/N$を約分した分数に変化させればよいです。
例えば,$M = 4, N = 6$の場合は、2/3に変化させるための最小の回数を出力してください。
入力
入力は以下のような形式で与えられる。M N
ここで、$M,N$は整数であり、 $1 \le M,N \le 10^9$ を満たす。
出力
$1$を$M/N$に変えるまでに必要な最小の魔法の回数を出力してください。 もしどのような順序で魔法を使っても$M/N$に変化させることができない場合は、$-1$を出力してください。 最後に改行してください。
サンプル
サンプル1
入力
2 3
出力
4
(1),(2),(1),(2)の順に魔法を使うと 1 → 2 → 1/2 → 3/2 → 2/3となって2/3が得られます。3回以下の魔法で2/3を得る方法は無いので、これが最小です。
サンプル2
入力
10 7
出力
7
(1),(1),(2),(1),(1),(2),(1)の順に魔法を使うと1 → 2 → 3 → 1/3 → 4/3 → 7/3 → 3/7 → 10/7となって10/7が得られます。
サンプル3
入力
1000000000 999999999
出力
1000000000
サンプル4
入力
4 6
出力
4
$M, N$は互いに素とは限りません。
注意
テストケースのうち、ファイル名が"testcase-small-"で始まるものは、 $1 \le M,N \le 300$を満たします。提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。