1311: Count Subtractions

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:101 通过:10 通过率:9.901%

题目描述

GCD 是最小公倍数的英文简写,对于常见的 GCD 来说假设两个数为 a 和 b, 那么可以得到如下操作:
1、如果 a > b , a = a - b
2、如果 b > a, b = b - a
经过不断的进行 1 2 的循环操作,直到 a 和 b 相等。最后能得到一个 a 和 b 的最小公倍数(a = b),现在需要你去计算,在这里面 1 和 2 一共执行了多少次。

输入格式

输入第一行有两个整数 a 和 b .

输出格式

输出为 1 行,代表 a 和 b 总共执行 1 和 2 的次数。

输入样例 复制

3 8

输出样例 复制

4

数据范围与提示

对于样例的解释:

    初始 a = 3, b = 8, a < b, b -= a, a = 3, b = 5

            a = 3, b = 5, a < b, b -= a, a = 3, b = 2

            a = 3, b = 2, b < a, a -= b, a = 1, b = 2  

            a = 1, b = 2, b > a, b -= a, a = 1, b = 1

因此 1 和 2 总共操作的次数为 4 次  

1 <= a , b<= 1018

分类标签