← 返回题目列表

AtCoder · arc159_b

B. GCD 减法

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有变量 a 和 b。最初, a=A 和 b=B.

高桥将重复以下操作,同时两个 a 和 b 大于或等于 1.

  • 让 g 是最大公约数 a 和 b,并替换 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