問題一覧 > 通常問題

No.1047 Zero (Novice)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 383
作問者 : stoq / テスター : trineutron
2 ProblemId : 4134 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-05-07 17:14:41

問題文

Sくんは整数 N を持っています。はじめ、N=0 です。
Sくんは次の操作を1回以上の好きな回数行います。

・N を AN+B で置き換える。

何回かの操作後に、再び N=0 となりえるでしょうか？ なりえるならば最小の操作回数を、なりえないならば-1を出力してください。

入力

A B

A,B は整数
−109≤A,B≤109

出力

何回かの操作後に再び N=0 となるならば最小の操作回数を、そうでなければ-1を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
-1 2
出力
2

1回目の操作で N=−1⋅0+2=2 となり、
2回目の操作で N=−1⋅2+2=0 となります。
よって最小の操作回数は2です。

サンプル2
入力
10 10
出力
-1

再び N=0 となることはありません。

サンプル3
入力
1 0
出力
1

1回目の操作で N=1⋅0+0=0 となります。
よって最小の操作回数は1です。

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