102973: [Atcoder]ABC297 D - Count Subtractions

Problem Statement

You are given positive integers $A$ and $B$.

You will repeat the following operation until $A=B$:

• compare $A$ and $B$ to perform one of the following two:
  • if $A > B$, replace $A$ with $A-B$;
  • if $A < B$, replace $B$ with $B-A$.

How many times will you repeat it until $A=B$? It is guaranteed that a finite repetition makes $A=B$.

Constraints

• $1 \le A,B \le 10^{18}$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$A$ $B$

Output

Print the answer.

Sample Input 1

3 8

Sample Output 1

4

Initially, $A=3$ and $B=8$. You repeat the operation as follows:

• $A<B$, so replace $B$ with $B-A=5$, making $A=3$ and $B=5$.
• $A<B$, so replace $B$ with $B-A=2$, making $A=3$ and $B=2$.
• $A>B$, so replace $A$ with $A-B=1$, making $A=1$ and $B=2$.
• $A<B$, so replace $B$ with $B-A=1$, making $A=1$ and $B=1$.

Thus, you repeat it four times.

Sample Input 2

1234567890 1234567890

Sample Output 2

0

Note that the input may not fit into a 32-bit integer type.

Sample Input 3

1597 987

Sample Output 3

15

问题描述

给你两个正整数$A$和$B$。

你将重复执行以下操作，直到$A=B$：

• 比较$A$和$B$，执行以下两个操作之一：
  • 如果$A > B$，将$A$替换为$A-B$；
  • 如果$A < B$，将$B$替换为$B-A$。

你需要重复执行多少次才能使$A=B$？保证经过有限次重复后可以使得$A=B$。

约束

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

输入

输入通过标准输入给出，格式如下：

$A$ $B$

输出

输出答案。

样例输入 1

3 8

样例输出 1

4

初始时，$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$。

因此，你需要重复执行四次。

样例输入 2

1234567890 1234567890

样例输出 2

0

注意输入可能不适应32位整数类型。

样例输入 3

1597 987

样例输出 3

15