配点 : $400$ 点

問題文

変数 $a,b$ があり、初め $a=A, b=B$ です。

高橋君は $a,b$ がともに $1$ 以上の間、次の操作を繰り返すことにしました。

• $a$ と $b$ の最大公約数を $g$ とする。そして、$a,b$ をそれぞれ $a-g,b-g$ に置き換える。

操作は何回行われますか。

制約

• $1 \leq A,B \leq 10^{12}$
• $A,B$ は整数

入力

入力は以下の形式で標準入力から与えられる。

$A$ $B$

出力

答えを出力せよ。

15 9

2

$a=15,b=9$ の状態から以下のように操作が行われます。

• $g=3$ とする。そして、$a,b$ がそれぞれ $12(=15-3),6(=9-3)$ に置き換えられる。
• $g=6$ とする。そして、$a,b$ がそれぞれ $6(=12-6),0(=6-6)$ に置き換えられる。$b$ が $1$ 以上でなくなったため、操作の繰り返しはここで終了する。

1 1

1

12345678910 10987654321

36135