分数: 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