题解：CF2039D Shohag Loves GCD

· · 题解

数论 + 贪心构造

设最终的答案数组为 b。

手玩一下数据：

当 i=1 时，显然对于任意的 j \ (j \gt i) 都满足 \gcd(i,j)=1，那么要保证 b_1 \ne \gcd(b_1,b_j)，即保证 \forall j \in [2,n] , b_1 \nmid b_j。根据贪心策略不难想到让 b_1 取序列 a 中的最大值。

当 i=2 时，显然对于所有的 j \ (j \gt i \wedge i \mid j) 满足 \gcd(2,j)=2，那么要保证 b_2 \ne \gcd(b_2,b_j)，即保证 \forall j \ (j\in [4,n] \wedge i \mid j) , b_2 \nmid b_j。根据贪心策略将 b_2 设置为序列 a 中次大值。

当 i=3 时，同样地，显然对于所有的 j \ (j \gt i \wedge i \mid j) 满足 \gcd(3,j)=3，那么要保证 b_3 \ne \gcd(b_3,b_j)，即保证 \forall j \ (j\in [6,n] \wedge i \mid j) , b_3 \nmid b_j。同时，由于 3 是质数，对于任意的 k \ (k \lt i) 都满足 \gcd(i,k)=1，那么要保证 b_1 \ne \gcd(b_k,b_j)，显然这个式子一定成立，因为 \gcd(x,y) \le \min(x,y) 且前面条件中保证了只有 b_1 能取序列 a 中的最大值。也就是说，只要 i 是质数，那么 b_i 取序列 a 中的次大值即为最优解。因此根据贪心策略 b_3 设置为序列 a 中次大值。

当 i=4 时，显然对于所有的 j \ (j \gt i \wedge i \mid j) 满足 \gcd(4,j)=4，那么要保证 b_4 \ne \gcd(b_4,b_j)，即保证 \forall j \ (j\in [8,n] \wedge i \mid j) , b_4 \nmid b_j。由于 i=4 是合数，因而 b_i 的取值不能和 b_d 的取值相同，其中 d \lt i \wedge d \mid i。因而 b_4 的最优取值就是序列 a 中的次次大值。

归纳一下，只要 i 为质数，那么 b_i 取序列 a 中的次大值；若 i 为合数，则 b_i 的取值要比 i 的所有约数 j 中对应的 b_j 的最小值 mn 还要小，再根据贪心策略，让 b_i 尽可能大，即让 b_i 取序列 a 中小于 mn 的最大值。

具体实现：我们可以将 a 数组降序排序得到 a' 数组，用 ans_i 记录 b_i 是取自序列 a' 中的哪个下标的值。显然 ans_1=1，而对于后续更新过程考虑 DP 转移即可。

ans 数组的 DP 转移方程：ans_j=\max \{ans_i+1 \}，其中 j 为 i 的倍数。

那么无解就很好判定了，显然当 \exist i \in [1,n] ,ans_i \gt m 时无解。

若采用枚举倍数的做法，调和级数时间复杂度 O(n\log n)。当然也可以线性筛做到 O(n)。

PS：分析到这你就会发现实际上本题的 ans 数组和给定的 m 个数毫无关系，ans 数组你完全可以直接预处理。

const int N=1e5+5;
int n,m;
int a[N];
int ans[N];
void solve(){
    cin>>n>>m;
    rep(i,1,m) cin>>a[i];
    sort(a+1,a+1+m,greater<int>());
    ans[1]=1;
    int mx=0;
    rep(i,1,n){
        for(int j=2*i;j<=n;j+=i){
            ans[j]=max(ans[j],ans[i]+1);
            mx=max(mx,ans[j]);
        }
    }
    if(mx>m) cout<<-1;
    else rep(i,1,n) cout<<a[ans[i]]<<" ";
}