GCD を \(x\) にするためには以下の条件を満たす必要があります。

• \(A_i\) が \(x\) で割り切れる。
• \(x\) で割り切れる \(A\) の要素が \(K\) 個以上存在する。

このような \(x\) のうち最大のものが答えとなります。

上記の条件を計算するためにいくつかの DP テーブルを前計算していきます。以降では \(M = \max(A)\) とします。
\(s_n\) を \(A\) に含まれる \(n\) の個数とします。\(s_n\) は配列を用いて \(A\) の要素を走査しながらカウントしていけばよいので \(\mathrm{O}(N + M)\) で行えます。
次に \(t_n\) を \(A\) に含まれる \(n\) の倍数の個数とします。以降では \(d \vert n\) を「\(d\) は \(n\) を割り切る」という意味で使います。\(t_n\) と \(s_n\) の間には

\[t_d = \sum_{d \vert n} s_n\]

という関係式が成り立つので、次の 2 重 for 文の要領で \(t_n\) を全て計算できます。

for(int d = 1; d <= M; d++) {
  for(int n = d; n <= M; n += d) {
    t[d] += s[n];
  }
}

この二重 for 文の計算量はいわゆる調和級数(の \(M\) 倍)で抑えられるので \(\mathrm{O}(M \log M)\) です。

最後に \(u_n\) を \(A_i = n\) の時の答えとします。\(u_n\) と \(t_n\) の間には

\[ u_n =\max(\left\lbrace d \vert n かつ t_d \geq K を満たす d\right\rbrace) \]

という関係式が成り立つので、\(u_n\) は以下の 2 重 for 文で計算できます。この二重 for 文の計算量もまた \(\mathrm{O}(M \log M)\) です。

for(int d = 1; d <= M; d++) {
  if(t[d] < K) continue;
  for(int n = d; n <= M; n += d) {
    u[n] = max(u[n], d);
  }
}

あとは各 \(i\) について \(u_{A_i}\) を出力すればよいです。

以上の方法でこの問題を時間計算量 \(\mathrm{O}(N + M \log M)\), 空間計算量 \(\mathrm{O}(N + M)\) で解くことが出来て、これは十分高速です。

• 実装例(C++)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (auto& a : A) cin >> a;
  int M = *max_element(begin(A), end(A));
  vector<int> s(M + 1), t(M + 1), u(M + 1);
  for (auto& a : A) s[a]++;
  for (int d = 1; d <= M; d++) {
    for (int n = d; n <= M; n += d) {
      t[d] += s[n];
    }
  }
  for (int d = 1; d <= M; d++) {
    if (t[d] < K) continue;
    for (int n = d; n <= M; n += d) {
      u[n] = max(u[n], d);
    }
  }
  for (auto& a : A) cout << u[a] << "\n";
}

以下は余談ですが、この問題は別解が多くあります。

• 時間計算量が \(\mathrm{O}(N \sqrt{M} + M \log M)\) 掛かる解法
• 空間計算量が \(\mathrm{O}(M \log M)\) 掛かる解法
  

いずれの解法も工夫した実装を行えば 2 秒の TL に間に合いますが、特に前者は実装によっては TLE すると思います。ご了承ください。