こんにちは！ mnbd（@mnbbbbbd）です。
AIZU ONLINE JUDGEの「ALDS1_1_B 最大公約数」を解いてみましたので、その回答と解説をご紹介いたします。
プログラミング初心者なので、もっといい回答があるに違いありません。
あくまでも「動作はする」サンプルとしてご覧ください。
問題文
２つの自然数 x, y を入力とし、それらの最大公約数を求めるプログラムを作成してください。
２つの整数 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 が１つの空白区切りで１行に与えられます。出力
最大公約数を１行に出力してください。ヒント
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_B
整数 x, y について、x ≥ y ならば x と y の最大公約数は y と x % y の最大公約数に等しい。ここで x % y は x を y で割った余りである。
解答
#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）
以上です。
読んでいただきありがとうございました！
