分数: 400 点
问题陈述
给你正整数 A 和 B.
您将重复以下操作,直到 A=B:
- 比较 A 和 B 执行以下两项之一:
- if A > B,替换 A 与 A-B;
- if 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