分数: 100 点
问题陈述
给你正整数 N 和 M.
如果重复以下操作,而 M 不是 0,查找执行的操作数。
- 让 x 为余数 N 除以 M。替换的值 M 与 x.
可以证明 M 变为 0 经过有限次数的操作。
约束
- 1 \leq N, M \leq 1000
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
输出
输出答案。
示例输入 1
8 5
示例输出 1
3
最初, N = 8 和 M = 5.
时的余数 8 除以 5 is 3,所以 M = 3 一次操作后。
时的余数 8 除以 3 is 2,所以 M = 2 两次操作后。
时的余数 8 除以 2 is 0,所以 M = 0 经过三次操作。
因此,输出 3 作为答案。
示例输入 2
14 6
示例输出 2
2
示例输入 3
460 33
示例输出 3
5