【AtCoder】ABC 460 A - Mod While Positive

2026-06-08

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 15 / NoviSteps: 6Q / 配点: 100 点

問題概要

正整数 $N, M$ が与えられる。 $M$ の値が $0$ でない間以下の操作を繰り返すとき、操作を行う回数を求めよ。

$N$ を $M$ で割った余りを $x$ とする。 $M$ の値を $x$ で置き換える。

なお、この操作を有限回行うことにより $M = 0$ になることが証明できる。

制約

$1 \leq N, M \leq 1000$
入力される値はすべて整数

考察

while文を用いて、問題通りに操作を繰り返せばよい。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.// ======================================== //
5. 
6.int main()
7.{
8.    int N, M;
9.    cin >> N >> M;
10. 
11.    int ans = 0;
12.    while (M > 0)
13.    {
14.        int x = N % M;
15.        M = x;
16.        ans++;
17.    }
18. 
19.    cout << ans << endl;
20. 
21.    return 0;
22.}