题目描述

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

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

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

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

输入格式

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

$A$ $B$

输出格式

答えを出力せよ。

题目大意

给你 $A,B$ 两个数，进行以下操作 :

1. 如果 $A>B$,那么 $A=A-B$ 。
2. 如果 $A<B$,那么 $B=B-A$ 。

请输出经过多少次操作后 $A=B$ 。

输入格式

两个整数。

A B

输出格式

答案，一个整数。

by X_Z_Y

3 8

4

1234567890 1234567890

0

1597 987

15

提示

制約

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

Sample Explanation 1

始め、$A=3,B=8$ です。操作は以下のように行われます。 - $A\ <\ B$ であるため、$B$ を $B-A=5$ で置き換える。$A=3,B=5$ となる。 - $A\ <\ B$ であるため、$B$ を $B-A=2$ で置き換える。$A=3,B=2$ となる。 - $A\ >\ B$ であるため、$A$ を $A-B=1$ で置き換える。$A=1,B=2$ となる。 - $A\ <\ B$ であるため、$B$ を $B-A=1$ で置き換える。$A=1,B=1$ となる。 よって、操作回数は $4$ 回です。

Sample Explanation 2

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