牛客挑战赛47 B.又一道gcd题

传送门

因为是,所以选出来的数一定都是答案的倍数

那么有一个很直观的方法

由于枚举每个数的约数复杂度是根号的

那就直接枚举约数,让

最后如果就代表有个数含有因子

那么选出这些数来一定是

然后从后往前更新答案

因为可以作为个数的,那么去掉任何一个属,也还可以作为选出个数的

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,ok[maxn],ans[maxn];
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        int x; cin >> x;
        for(int j=1;j*j<=x;j++)
        {
            if( x%j!=0 )    continue;
            ok[j]++;
            if( j!=x/j )    ok[x/j]++;
        }
    }
    for(int i=100000;i>=1;i-- )
        if( !ans[ok[i]] )    ans[ok[i]] = i;
    for(int i=n;i>=2;i--)
        ans[i] = max( ans[i],ans[i+1] );
    for(int i=2;i<=n;i++)    cout << max(1,ans[i]) << " ";    
}