/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
正整数 N, M が与えられます。
M の値が 0 でない間以下の操作を繰り返すとき、操作を行う回数を求めてください。
- N を M で割った余りを x とする。M の値を x で置き換える。
なお、この操作を有限回行うことにより M = 0 になることが証明できます。
制約
- 1 \leq N, M \leq 1000
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
8 5
出力例 1
3
はじめ、N = 8, M = 5 です。
8 を 5 で割った余りは 3 であるため、1 回操作を行うと M = 3 となります。
8 を 3 で割った余りは 2 であるため、2 回操作を行うと M = 2 となります。
8 を 2 で割った余りは 0 であるため、3 回操作を行うと M = 0 となります。
したがって、3 を答えとして出力します。
入力例 2
14 6
出力例 2
2
入力例 3
460 33
出力例 3
5
Score : 100 points
Problem Statement
You are given positive integers N and M.
If the following operation is repeated while the value of M is not 0, find the number of operations performed.
- Let x be the remainder when N is divided by M. Replace the value of M with x.
It can be proved that M becomes 0 after a finite number of operations.
Constraints
- 1 \leq N, M \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Output the answer.
Sample Input 1
8 5
Sample Output 1
3
Initially, N = 8 and M = 5.
The remainder when 8 is divided by 5 is 3, so M = 3 after one operation.
The remainder when 8 is divided by 3 is 2, so M = 2 after two operations.
The remainder when 8 is divided by 2 is 0, so M = 0 after three operations.
Thus, output 3 as the answer.
Sample Input 2
14 6
Sample Output 2
2
Sample Input 3
460 33
Sample Output 3
5