AtCoder ABC 120 B - K-th Common Divisor (6Q, 灰色, 200 点)

全探索でやってしまうのが楽だと思われる。

• 問題へのリンク

問題概要

正の整数 が与えられる。

をともに割り切る整数のうち、 番目に大きいものを求めよ。

制約

• 
• をともに割り切る整数のうち、 番目に大きいものが存在する

考えたこと

全探索で解いてしまうのが楽だと思う。大きい方から数えて 番目の値を求めたいので、大きい方から探索していこう。

具体的には、 として、 に対して、次のようにすればよい。

---

1. が をともに割り切るかどうかを確認する
2. 割り切るならば をデクリメントする
3. になったならば、そのときの の値を出力する

---

計算時間を簡単に見積もろう。 なので、たかだか 100 通りの整数値をチェックすればよい。この程度の探索はできる。

コード

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

int main() {
  int A, B, K;
  cin >> A >> B >> K;
  for (int x = min(A, B); x >= 1; --x) {
    if (A % x == 0 && B % x == 0) {
      --K;
      if (K == 0) {
        cout << x << endl;
        return 0;
      }
    }
  }
}