由于 \(a_i \le 10^6\)，故可以一遍求出 \([1,10^6]\) 内每个数的因数以及这个数的倍数在 \(a\) 中的出现次数。求完后对每个 \(a_i\) 暴力枚举因数，判断其倍数出现次数是否超过 \(k\) 并更新答案即可。
总时间复杂度 \(O(N\log N+nd(a_i))\)，其中 \(N=10^6\)，又由于 \(a_i\le 10^6\)，故 \(\max \{ d(a_i) \} \le 240\)，可以通过本题。如果后半部分预处理完 \([1,10^6]\) 内所有答案再输出，则复杂度 \(O(N\log N+n)\)，但实际运行稍慢。以下代码为第一种写法。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define N 1000000using namespace std;vector<int> p[N + 10];
int n,k,a[N * 2 + 10],f[N + 10],g[N + 10];int main()
{cin >> n >> k;for( int i = 1 ; i <= n ; i ++ )cin >> a[i],f[a[i]] ++;for( int i = 1 ; i <= N ; i ++ )for( int j = i ; j <= N ; j += i )p[j].push_back( i ),g[i] += f[j];for( int i = 1 ; i <= n ; i ++ ){for( int j = p[a[i]].size() - 1 ; j >= 0 ; j -- )if( g[p[a[i]][j]] >= k ){cout << p[a[i]][j] << '\n';break;}}return 0;
}