\(A_i\) の最大値を \(A_{\text{max}}\) とおきます。また、\(j=1,2,\dots,A_{\text{max}}\) について、\(A_i=j\) を満たす \(i\) の個数を \(C_j\) とおきます。

まず、\(j=1,2,\dots,A_{\text{max}}\) それぞれについて、最大公約数が \(j\) になりうるか判定するという方針が考えられます。しかしこの方針では解きにくいので、代わりに最大公約数が \(j\) の倍数になりうるか判定する方針を取ります。最大公約数が \(j\) の倍数になりうるような最大の \(j\) を \(j'\) とおくと、実はこの \(j'\) は求める答えと一致します。なぜなら、「最大公約数が \(j'\) の倍数になりうる」ことと「\(j'\) より大きい全ての \(j\) について、最大公約数は \(j\) の倍数になりえない」ことから「最大公約数が \(j'\) になりうる」ことが導けるからです。

では、最大公約数が \(j\) の倍数になりうるかどうかはどのように判定すればよいでしょうか？「最大公約数が \(j\) の倍数になる」ことと「選んだ \(K\) 個の整数がすべて \(j\) の倍数である」ことは同値なので、\(C_j+C_{2j}+\dots+C_{\lfloor\frac{A_{\text{max}}}{j} \rfloor j}\) が \(K\) 以上であるかを判定すればよいです。\(\displaystyle \sum_{j=1}^{A_{\text{max}}} \lfloor\frac{A_{\text{max}}}{j} \rfloor = O(A_{\text{max}} \log A_{\text{max}})\) なので（調和級数）、各 \(j\) に対して愚直に \(C_j+C_{2j}+\dots+C_{\lfloor\frac{A_{\text{max}}}{j} \rfloor j}\) を計算しても間に合います。

よってこの問題を \(O(N+A_{\text{max}} \log A_{\text{max}})\) で解くことができました。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main() {
    int N, K; 
    cin >> N >> K;
    const int MAX = 1e6;
    vector<int> cnt(MAX + 1);
    for (int i = 0; i < N; i++) {
        int A; 
        cin >> A;
        cnt[A]++;
    }
    int ans = 0;
    for (int i = 1; i <= MAX; i++) {
        int sum = 0;
        for (int j = i; j <= MAX; j += i) sum += cnt[j];
        if (K <= sum) ans = i;
    }
    cout << ans << endl;
}