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

传送门

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

那么有一个很直观的方法

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

那就直接枚举约数 $k$ ,让 $ok[k]++$

最后如果 $ok[i]$ 就代表有 $ok[i]$ 个数含有因子 $i$

那么选出这些数来一定是 $gcd$

然后从后往前更新答案

因为可以作为 $i+1$ 个数的 $gcd$ ,那么去掉任何一个属,也还可以作为选出 $i$ 个数的 $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]) << " ";    
}