减法计数

题目描述

给定正整数 $A$ 和 $B$。

重复以下操作直到 $A=B$：

比较 $A$ 和 $B$，执行以下两种操作之一：

• 如果 $A \gt B$，将 $A$ 替换为 $A-B$；
• 如果 $A \lt B$，将 $B$ 替换为 $B-A$。

直到 $A=B$ 为止需要重复多少次操作？可以保证经过有限次重复后必定有 $A=B$。

输入格式

输入按以下格式从标准输入给出：

$A$ $B$

输出格式

输出答案。

样例

3 8

4

初始时 $A=3$，$B=8$。操作按如下方式重复：

• $A \lt B$，因此将 $B$ 替换为 $B-A=5$，得到 $A=3$，$B=5$。
• $A \lt B$，因此将 $B$ 替换为 $B-A=2$，得到 $A=3$，$B=2$。
• $A \gt B$，因此将 $A$ 替换为 $A-B=1$，得到 $A=1$，$B=2$。
• $A \lt B$，因此将 $B$ 替换为 $B-A=1$，得到 $A=1$，$B=1$。

因此，一共重复了四次。

1234567890 1234567890

0

注意输入可能超出 32 位整数类型的范围。

1597 987

15

数据范围

• $1 \le A,B \le 10^{18}$
• 输入中的所有值均为整数。