問題一覧 > 通常問題

No.141 魔法少女コバ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 258
作問者 : koba-e964
16 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≤M,N≤109 を満たす。

出力

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≤M,N≤300を満たします。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。