题解：CF2039D Shohag Loves GCD

lgx57 · 2024-12-01 19:38:20 · 题解

简单题。

注意到答案与数根本没有关系，从而想到先把数从大到小排序。

接下来我们一个一个填数，由于字典序要最大，所以第一位肯定填最大的数。

注意到 \gcd(x,y) \le \min(x,y)，于是可以在此基础上构造。令 ans_i=\text{比 } \displaystyle\max_{j \mid i,j <i} ans_j \text{ 小的第一个数}。容易证明，这个构造合法并且是字典序最大的。

于是我们用 O(n \sqrt n) 的复杂度解决了这个问题。

void sol(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++) ans[i]=0;
    for (int i=1;i<=m;i++) cin>>a[i];
    sort(a+1,a+m+1,greater<int>());
    ans[1]=1;
    for (int i=2;i<=n;i++){
        int ma=0;
        for (int j=1;j*j<=i;j++){
            if (i%j==0){
                ma=max(ma,max(ans[j],ans[i/j]));
            }
        }
        ans[i]=ma+1;
        if (ans[i]>m) return cout<<-1<<endl,void();
    }
    for (int i=1;i<=n;i++) cout<<a[ans[i]]<<' ';
    cout<<endl;
}