题解：CF2039D Shohag Loves GCD
从给定集合中选数并构造序列 $\{a_i\}$，需要满足 $a_{\gcd (i,j)} \neq \gcd(a_i,a_j) \mid \forall 1 \le i < j \le n$ 并且构造出的序列字典序最大。
不妨从反面分析，考虑满足 $a_{\gcd (i,j)} = \gcd (a_i,a_j)$。当 $i \mid j$ 时，$\gcd (i,j) = i$，$a_i \mid a_j$。进一步的，当 $i \nmid j$ 时，是否也存在一个 $i$，满足 $a_{\gcd (i,j)} = \gcd (a_i,a_j)$ 呢？
假设存在这个 $i$，我们设 $g = \gcd (i,j)$，那么 $a_g = \gcd (a_i,a_j)$ 且 $g < i$。由于 $g \mid i$，等价于 $g = \gcd (g,i)$，由上面的结论可知 $a_{\gcd (g,i)} = \gcd (a_g,a_i)$。此时与题目的条件不符合，故假设不成立。
所以说在构造 $a_i$ 时，只需要考虑序列以 $i$ 的因数（且小于 $i$）为下标的数，预处理因数即可。在构造的时候，我们可以将所有以 $i$ 的因数为下标的数放入 $\mathrm{set}$ 中，然后从最大的数开始，查找到第一个未出现在集合中的数即可退出循环。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int M = 1e5;
const int MOD = 1e9 + 7;
inline int read ();
vector <int> ans,p[MAX];
int t,n,m,a[MAX];
int main ()
{
for (int i = 1;i <= M;++i)
for (int j = i + i;j <= M;j += i) p[j].push_back (i);
t = read ();
while (t--)
{
n = read ();m = read ();
for (int i = 1;i <= m;++i) a[i] = read ();
sort (a + 1,a + 1 + m);ans.clear ();
for (int i = 1;i <= n;++i)
{
set <int> invaild;
for (auto item : p[i]) invaild.insert (ans[item - 1]);
for (int j = m;j;--j)
{
if (invaild.find (a[j]) == invaild.end ())
{
ans.push_back (a[j]);
break;
}
}
if (ans.size () != i) break;
}
if (ans.size () != n) puts ("-1");
else {for (auto item : ans) printf ("%d ",item);puts ("");}
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
