← 返回题目列表

AtCoder · abc460_a

A. Mod 为正值

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

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