← 返回题目列表

AtCoder · abc297_d

G. 计算减法

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

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