B - Greatest Common Divisor

cpaojalds1

最終更新日

Table of Contents

Loading...

問題

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

問題文

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

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

制約

サンプル

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; }