B - GCD Subtraction 解説 /

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

配点 : 400 点

問題文

変数 a,b があり、初め a=A, b=B です。

高橋君は a,b がともに 1 以上の間、次の操作を繰り返すことにしました。

  • a と b の最大公約数を g とする。そして、a,b をそれぞれ a-g,b-g に置き換える。

操作は何回行われますか。

制約

  • 1 \leq A,B \leq 10^{12}
  • A,B は整数

入力

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

A B

出力

答えを出力せよ。

入力例 1

15 9

出力例 1

2

a=15,b=9 の状態から以下のように操作が行われます。

  • g=3 とする。そして、a,b がそれぞれ 12(=15-3),6(=9-3) に置き換えられる。
  • g=6 とする。そして、a,b がそれぞれ 6(=12-6),0(=6-6) に置き換えられる。b が 1 以上でなくなったため、操作の繰り返しはここで終了する。

入力例 2

1 1

出力例 2

1

入力例 3

12345678910 10987654321

出力例 3

36135

Score : 400 points

Problem Statement

We have variables a and b. Initially, a=A and b=B.

Takahashi will repeat the following operation while both a and b are greater than or equal to 1.

  • Let g be the greatest common divisor of a and b, and replace a and b with a-g and b-g, respectively.

How many times will he perform the operation?

Constraints

  • 1 \leq A,B \leq 10^{12}
  • A and B are integers.

Input

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

A B

Output

Print the answer.

Sample Input 1

15 9

Sample Output 1

2

We start with a=15,b=9 and perform the following.

  • Let g=3, and replace a and b with 12(=15-3) and 6(=9-3), respectively.
  • Let g=6, and replace a and b with 6(=12-6) and 0(=6-6), respectively. b is no longer greater than or equal to 1, so the iteration terminates.

Sample Input 2

1 1

Sample Output 2

1

Sample Input 3

12345678910 10987654321

Sample Output 3

36135