配点 : $400$ 点

問題文

正整数 $A,B$ が与えられます。

あなたは、$A=B$ になるまで以下の操作を繰り返します。

• $A,B$ の大小関係に応じて、次の $2$ 個のうちどちらかの処理を行う。- $A > B$ ならば、$A$ を $A-B$ で置き換える。
  • $A < B$ ならば、$B$ を $B-A$ で置き換える。
• $A > B$ ならば、$A$ を $A-B$ で置き換える。
• $A < B$ ならば、$B$ を $B-A$ で置き換える。

$A=B$ になるまで、操作を何回行うか求めてください。ただし、有限回の操作で $A=B$ になることが保証されます。

制約

• $1 \le A,B \le 10^{18}$
• 入力はすべて整数

入力

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

$A$ $B$

出力

答えを出力せよ。

3 8

4

始め、$A=3,B=8$ です。操作は以下のように行われます。

• $A であるため、$B$を$B-A=5$で置き換える。$A=3,B=5$ となる。
• $A であるため、$B$を$B-A=2$で置き換える。$A=3,B=2$ となる。
• $A>B$ であるため、$A$ を $A-B=1$ で置き換える。$A=1,B=2$ となる。
• $A であるため、$B$を$B-A=1$で置き換える。$A=1,B=1$ となる。

よって、操作回数は $4$ 回です。

1234567890 1234567890

0

入力が 32bit 整数型に収まらないことがあることに注意してください。

1597 987

15