题目解析

问题重述

给定 $n$ 和集合 $S$（包含 $m$ 个不同的整数，每个数在 $[1, n]$ 范围内），需要构造一个长度为 $n$ 的数组 $a$，满足：

$1$. 对所有 $1 \le i \le n$，有 $a_i \in S$ $2$. 对所有 $1 \le i < j \le n$，有 $a_{\gcd(i, j)} \neq \gcd(a_i, a_j)$

要求输出字典序最大的解，若无解输出 $-1$。

---

条件化简

必要条件

首先考虑 $i$ 整除 $j$ 的情况。当 $i \mid j$ 时，$\gcd(i, j) = i$，条件变为：

$$a_i \neq \gcd(a_i, a_j)$$

这意味着 $a_i$ 不能整除 $a_j$，否则 $\gcd(a_i, a_j) = a_i$，违反条件。

结论$1$：对于任意 $i \mid j$，$a_i$ 不能整除 $a_j$。

充分性证明

现在证明这个条件也是充分的。

假设存在一对 $(i, j)$ 违反原条件，即：

$$a_{\gcd(i, j)} = \gcd(a_i, a_j)$$

令 $g = \gcd(i, j)$。则 $g \mid i$ 且 $g \mid j$。考虑对 $(g, i)$：

• $\gcd(g, i) = g$，所以 $a_{\gcd(g,i)} = a_g$
• $\gcd(a_g, a_i) = a_g$（因为 $a_g$ 整除 $a_i$？需要验证）

由于 $a_g$ 是 $\gcd(a_i, a_j)$ 的因子，而 $\gcd(a_i, a_j)$ 整除 $a_i$，所以 $a_g \mid a_i$。因此 $\gcd(a_g, a_i) = a_g$。

于是 $(g, i)$ 也违反条件，且此时 $g \mid i$。

结论$2$：如果原条件被违反，那么存在一对 $(p, q)$ 且 $p \mid q$ 也违反条件。

因此，只要对所有整除对 $(i, j)$（$i \mid j$）满足 $a_i$ 不整除 $a_j$，则原条件对所有 $(i, j)$ 都成立。

核心条件：对所有 $i \mid j$，$a_i \nmid a_j$。

---

链式结构

考虑一条倍数链：

$$i_1 \mid i_2 \mid i_3 \mid \cdots \mid i_k$$

在这样一条链上，根据核心条件，$a_{i_1}$ 不能整除 $a_{i_2}$，$a_{i_2}$ 不能整除 $a_{i_3}$，等等。

由于 $a_i$ 都来自同一个有限集合 $S$，这条链的长度不能超过 $|S| = m$。更精确地说，链上每个位置的数必须互不相同，且必须形成一个互不整除的序列。

最长链分析：

考虑从 $1$ 开始，每次乘以一个质因数的链：

$$1 \to 2 \to 4 \to 8 \to \cdots \to 2^{\lfloor \log_2 n \rfloor} $$

这条链的长度是 $\lfloor \log_2 n \rfloor + 1$。由于每一步乘以 $2$（质因数），这实际上是最长可能链——因为要最大化链长，每一步应乘以最小的质数 $2$。

因此，最大链长为 $\lfloor \log_2 n \rfloor + 1$。

存在性条件：为了构造合法序列，必须有足够多的不同数来填充最长链，即：

$$m \ge \lfloor \log_2 n \rfloor + 1$$

若 $m < \lfloor \log_2 n \rfloor + 1$，则无解，输出 $-1$。

---

构造策略

关键观察

对于位置 $i$，考虑所有 $i$ 的倍数链中以 $i$ 结尾的最长链。这条链的长度决定了 $a_i$ 在 $S$ 中的排名。

定义 $p(i)$ = $i$ 的质因数个数（计重数）。例如：

• $p(1) = 0$
• $p(2) = 1$
• $p(4) = 2$
• $p(12) = p(2^2 \cdot 3) = 3$

那么以 $i$ 结尾的最长链长度恰好是 $p(i) + 1$。这是因为可以从 $1$ 开始，每次添加一个质因数到达 $i$。

赋值规则

设 $S$ 中元素从小到大为 $s_1 < s_2 < \cdots < s_m$。

为了字典序最大，我们应该把较大的数放在较小的下标上。同时，在倍数链上，数值必须严格递减（否则会违反整除条件）。

因此，对于位置 $i$，我们赋值为：

$$a_i = s_{m - p(i)}$$

这样：

• $p(i)$ 越大，$a_i$ 越小（因为要满足链上递减）
• 当 $i = 1$ 时，$p(1) = 0$，$a_1 = s_m$（最大数）
• 当 $i = 2$ 时，$p(2) = 1$，$a_2 = s_{m-1}$
• 当 $i = 4$ 时，$p(4) = 2$，$a_4 = s_{m-2}$
• 依此类推

正确性验证

$1$. 整除链上的条件：若 $i \mid j$，则 $p(j) \ge p(i) + 1$（因为 $j/i$ 至少包含一个质因数），所以 $m - p(j) \le m - p(i) - 1$，即 $a_j < a_i$。因此 $a_i$ 不整除 $a_j$（因为 $a_j$ 更小）。

$2$. 字典序最大：对于每个位置 $i$，$a_i$ 取到了在不破坏已赋值位置条件下的最大可能值。因为更早的位置（更小的 $i$）已经占用了更大的数。

---

算法实现

步骤

$1$. 预处理 $p(i)$ 数组：$p(i)$ = $i$ 的质因数个数（计重数） $2$. 读入 $n, m$ 和 $S$ $3$. 若 $m < \lfloor \log_2 n \rfloor + 1$，输出 $-1$ $4$. 否则，对 $i = 1$ 到 $n$，输出 $s_{m - p(i)}$

时间复杂度

• 预处理 $p$：$O(n \log \log n)$（埃氏筛）
• 每个测试用例：$O(n)$
• 总复杂度：$O(\sum n \log \log n) \le 3 \times 10^5 \times \log \log 10^5$

---

完整代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 9;
int p[N];  // p[i] = 质因数个数（计重数）

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> s(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> s[i];
    }
    
    // 检查是否有足够的数填充最长链
    if (m < __lg(n) + 1) {
        cout << -1 << '\n';
        return;
    }
    
    // 构造序列
    for (int i = 1; i <= n; i++) {
        cout << s[m - p[i]] << ' ';
    }
    cout << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    // 预处理 p[i]：质因数个数
    for (int i = 2; i < N; i++) {
        if (p[i]) continue;  // i 不是质数
        for (int j = i; j < N; j += i) {
            int x = j;
            while (x % i == 0) {
                x /= i;
                p[j]++;
            }
        }
    }
    
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

示例验证

样例$1$

$n=6, m=3, S=\{3,4,6\}$，$s=[3,4,6]$

预处理 $p$：

• $p(1)=0, p(2)=1, p(3)=1, p(4)=2, p(5)=1, p(6)=2$

构造：

• $a_1 = s_{3-0} = s_3 = 6$
• $a_2 = s_{3-1} = s_2 = 4$
• $a_3 = s_{3-1} = s_2 = 4$
• $a_4 = s_{3-2} = s_1 = 3$
• $a_5 = s_{3-1} = s_2 = 4$
• $a_6 = s_{3-2} = s_1 = 3$

输出：$6 4 4 3 4 3$ ✅

样例$2$

$n=1, m=1, S=\{1\}$

$p(1)=0$，$a_1 = s_1 = 1$ ✅

样例$3$

$n=2, m=1, S=\{2\}$

$\lfloor \log_2 2 \rfloor + 1 = 2$，但 $m=1 < 2$，无解 → $-1$ ✅

---

总结

本题的核心是将复杂的 $\gcd$ 条件转化为简洁的整除条件：对所有 $i \mid j$，$a_i \nmid a_j$。通过分析倍数链结构和质因数个数，得出构造方案：$a_i = s_{m - p(i)}$。这个构造既保证了合法性，又达到了字典序最大。