题目链接

题面：

题解：
统计每个因数出现的次数。
对于每个出现次数维护最大的因数。
逆向更新

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define pr make_pair
#define pb push_back
using namespace std;
const int maxn=1001000;
int p[maxn],c[maxn];
void fi(int x)
{
    int sq=sqrt(x);
    for(int i=1;i<=sq;i++)
    {
        if(x%i!=0) continue;
        p[i]++;
        if(i*i!=x)
            p[x/i]++;
    }
}

int main(void)
{
    int n,x;
    scanf("%d",&n);
    //求每个因数出现的次数
    for(int i=1;i<=n;i++)
        scanf("%d",&x),fi(x);
    //对每个次数记录最大的因数
    for(int i=1;i<maxn;i++)
        c[p[i]]=max(c[p[i]],i);
    //逆向更新
    for(int i=n-1;i>=1;i--)
        c[i]=max(c[i],c[i+1]);
    for(int i=1;i<=n;i++)
        printf("%d\n",c[i]);
    return 0;
}