ALDS1_1_B 最大公約数をC++で解いてみた[AIZU ONLINE JUDGE]

AIZU ONLINE JUDGE

こんにちは! mnbd(@mnbbbbbd)です。

AIZU ONLINE JUDGEの「ALDS1_1_B 最大公約数」を解いてみましたので、その回答と解説をご紹介いたします。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文

2つの自然数 x, y を入力とし、それらの最大公約数を求めるプログラムを作成してください。

2つの整数 x と y について、x ÷ d と y ÷ d の余りがともに 0 となる d のうち最大のものを、x と y の最大公約数(Greatest Common Divisor)と言います。例えば、35 と14 の最大公約数 gcd (35, 14) は 7 となります。これは、35 の約数{1, 5, 7, 35}、14 の約数 {1, 2, 7, 14} の公約数 {1, 7} の最大値となります。

入力
x と y が1つの空白区切りで1行に与えられます。

出力
最大公約数を1行に出力してください。

ヒント
整数 x, y について、x ≥ y ならば x と y の最大公約数は y と x % y の最大公約数に等しい。ここで x % y は x を y で割った余りである。 

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_B

解答

#include <bits/stdc++.h>
using namespace std;

int gcd1(int x, int y) {
    int n = min(x, y);
    if(y == 0) {
        return x;
    }
    return gcd1(y, x % y);
}

int gcd2(int x, int y) {
    if(x < y) {
        swap(x, y);
    }
    while(y > 0) {
        int r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << gcd2(x, y) << endl;
    return 0;
}

感想

単純に自然数でxとyの値を割っていくと、計算量が多すぎて合格できないので、ヒントを利用しなければなりませんでした。

ヒントを頼りに書いたgcd1関数で合格できました。

ページにある「一般解説」にアルゴリズムが載っていますので、gcd2関数のように実装すればそちらでも合格が得られます。

その他の点では、2つの値を最小値を得るmin関数や2つの値を入れ替えるswap関数について知りました。

まとめ

AIZU ONLINE JUDGEの「ALDS1_1_B 最大公約数」を解いてみましたので、その回答と解説をご紹介いたします。

少しずつですが、プログラミングの勉強をしています。
まだ初心者ですが、よかったらつながっていただけると嬉しいです。
Twitterアカウント(@mnbbbbbd

以上です。
読んでいただきありがとうございました!