No.1047 Zero (Novice)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 252
作問者 : stoqstoq / テスター : trineutrontrineutron
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$ は整数
$-10^9 \leq A,B \leq 10^9$

出力

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

サンプル

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

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

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

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

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

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

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