[LuoguP1414]又是毕业季II
sshwy
2019-03-04 14:16:14
# 分析
题目难点在于利用答案的单调性，显然$k$越小，$gcd$越大。
考虑记录每一个因数出现的次数，再用次数多的因数来更新次数少的因数（取$max$）.
复杂度$O(n\sqrt n)$.
# 代码
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10004,MXA=1000006;
int n,a,mxa;
int t[MXA],p[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a);
mxa=max(mxa,a);
for(int j=1;j*j<=a;j++){
if(j*j==a)t[j]++;
else if(a%j==0)t[j]++,t[a/j]++;
}
}
for(int i=1;i<=mxa;i++)p[t[i]]=i;
//相同出现次数，大的因数会自动把小的因数更新掉
for(int i=n-1;i>=1;i--)p[i]=max(p[i],p[i+1]);
//次数多的因数来更新次数少的因数
for(int i=1;i<=n;i++)printf("%d\n",p[i]);
return 0;
}
```