問題一覧 > 通常問題

No.141 魔法少女コバ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 254
作問者 : koba-e964koba-e964
15 ProblemId : 228 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:19

問題文

魔法少女のコバは数を変化させる魔法を覚えました。コバが使える魔法は以下の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もしくは右上の雲マークをクリックしてアカウントを作成してください。