D - Count Subtractions 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

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

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

  • A,B の大小関係に応じて、次の 2 個のうちどちらかの処理を行う。
    • 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 となる。

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

入力例 2

1234567890 1234567890

出力例 2

0

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

入力例 3

1597 987

出力例 3

15

Score : 400 points

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