问题1311--Count Subtractions

1311: Count Subtractions

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

提交

题目描述

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 的次数。

样例输入 Copy

3 8

样例输出 Copy

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

来源/分类