B - Greatest Common Divisor

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_B (新しいタブで開く)

問題文

$x$ と $y$ の最大公約数を求めるプログラムを作成してね。

2 つの整数 $x, y$ について、 $x \div d$ と $y \div d$ の余りがともに 0 となる $d$ のうち最大のものを $x$ と $y$ の最大公約数と呼ぶ。
整数 $x, y$ について、 $x \gt y$ なら $x, y$ の最大公約数は $y, x \bmod y$ の最大公約数と等しい。

制約

• $1 \le x, y \le 10^9$

サンプル

I/O 1

147 105

21

考察

そのままやるだけ。
gcd 関数はもうあるけど、ちゃんと自分で書いた。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_1_B/judge/6379609/C++17 (新しいタブで開く)

int GCD(int x, int y) {
  if (x > y) swap(x, y);
  if (x == 0) return y;
  return GCD(y % x, x);
}

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