One can make the GCD \(x\) only if:

• \(A_i\) is divisible by \(x\).
• \(A\) has at least \(K\) elements divisible by \(x\).

The answer is the maximum among such \(x\).

To process the conditions above, we precalculate several DP tables. Let \(M = \max(A)\).
Let \(s_n\) be the number of occurrences of \(n\) in \(A\). \(s_n\) can be constructed in \(\mathrm{O}(N + M)\) using an array to count the occurrences while scanning \(A\).
Next, let \(t_n\) be the number of multiples of \(n\) in \(A\). Here, we will use the notation \(d \vert n\) as “\(d\) divides \(n\). \(t_n\) and \(s_n\) have the relation

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

so \(t_n\) can be computed in the manner of the following double for loops.

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

The complexity of this double for loop can be bounded by (\(M\) times) the so-called harmonic series, so the complexity is \(\mathrm{O}(M \log M)\).

Finally, let \(u_n\) be the answer for \(A_i = n\). \(u_n\) relates \(t_n\) as

\[ u_n =\max(\left\lbrace d \text{ such that }d \vert n\text{ and }t_d \geq K\right\rbrace), \]

so \(u_n\) can be computed by the following double for loop. The complexity of this for statement is also \(\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);
  }
}

All that left is to compute \(u_{A_i}\) for each \(i\).

This way, the problem can be solved in a total of \(\mathrm{O}(N + M \log M)\) time and \(\mathrm{O}(N + M)\) space, which is fast enough.

• Sample code (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";
}

As a side note, there are many alternative solutions, including:

• one with time complexity \(\mathrm{O}(N \sqrt{M} + M \log M)\),
• one with spacial complexity \(\mathrm{O}(M \log M)\).

both solutions will meet the two-second time limit if your implementation is good enough, but especially the former is subject to TLE (Time Limit Exceeded), so please be careful.