Submission #68199741

---

Source Code Expand

#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <ctime>
#include <set>
#include <setjmp.h>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
#define cty cout<<"Yes"<<endl
#define ctn cout<<"No"<<endl
#define dbg(x) cout<<#x<<" : "<<x<<endl
#define int long long
const int mxn = 1.2e6+10;
const int mod = 1e9+7;
double ST,ED;
int n,k;
int a[mxn];
int cnt[mxn];
int f[mxn];//f[x]表示x是a中f[x]个数的因子
int ans[mxn];
void LonelyLunar_solve(){
    cin>>n>>k;
    int mx = 0;
    for(int i = 1;i <= n; i++){
        cin>>a[i];
        cnt[a[i]]++;
        mx = max(mx,a[i]);
    }
    for(int i = 1;i <= mx; i++){
        for(int j = i;j <= mx; j+=i) f[i]+=cnt[j];
    }
    for(int i = mx;i >= 1; i--){
        if(f[i]>=k){
            for(int j = i;j <= mx; j+=i) if(ans[j]==0)ans[j] = i;
        }
    }
    for(int i = 1;i <= n; i++) cout<<ans[a[i]]<<endl;

}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int _ = 1;
	ST = clock();
	//cin>>_;
	while(_--){
		LonelyLunar_solve();
	}
	ED = clock();
	cerr<<1000*(ED-ST)/CLOCKS_PER_SEC<<"ms\n";
	return 0;
}

Submission Info

Judge Result