alds1_1_b aoj 最大公約数 ユークリッドの互除法

ALDS1_1_B | 最大公約数

ALDS1_1_B | 最大公約数
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_B

2つの整数が2つ与えられてその最大公約数をもとめる問題.

解説

詳しいアルゴリズムは以下を参照.

ユークリッドの互除法

計算量

$$
O(\log b)
$$

※ $b$ は剰余算の回数

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Int X, Y;

Int gcd(Int x, Int y) {
  if (x > y) swap(x, y);

  Int r;
  while (y > 0) {
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}

void input() {
  cin >> X >> Y;
}

void solve() {
  cout << gcd(X, Y) << endl;
}

int main() {
  input();
  solve();
  return 0;
}