题源

https://codeforces.com/contest/2173/problem/C

题意

Kanade在研究一个数字游戏。首先有两个数字$n$与$k$，以及具有$n$个整数的数组$a$，且该数组满足条件$1 \le a_i \le k$。你需要找到一种“完全数组”$B = \{b_1, b_2, \ldots, b_m\}$，不仅也满足$1\le b_i\le k$，还要满足下面两个条件：

• 对于$1\le i\le n$（即对于数组$a$中的每一个），至少$a_i$有一个因数在$B$当中。
• 对于$1\le j\le m$（即对于数组$B$中的每一个），所有$b_j$的正倍数（在$k$及以内的）至少在数组$a$出现一次。

你要找到满足这种条件的最小的$B$数组，或者说明不存在这种数组。

其他条件包括$1\le m\le n$，$1\le n\le 2\cdot 10^5$，$1\le k\le 10^9$，限时2秒。

提示

• 举个简单的例子解释题意，若有$k=6$，$a = \{2,3,4,6\}$，那么$B = \{2, 3\}$。$a$中每一个数字都至少有一个因数在$B$中，且$B$中所有元素在6及以下的倍数都在$a$中。
• 观察假设当$a$数组只有1个或2个元素时，$B$数组有什么规律。
• 思考$a$数组中有没有什么$B$数组必定包含的元素。

题解

对于$a$中最小的元素$x$，由于$x$已是最小，因此没有$x$的因数在$a$中。如果它不在$B$中，就违反了规则1。

因此$x$必定在$B$中。既然如此，根据规则2，不难知道$a$里面还应该出现$x$直到$k$的倍数，否则不存在这样的$B$。我们因此可以反过来验证$a$是否满足条件，并将这些$x$的倍数打标记。

验证完$x$后，$a$中未被打标记的都不是$x$的倍数。对于这些数，我们可以进行相同的操作——找到最小一个、反向验证。注意同一个数可以被多次标记。

对于C++中如何实现上述思路，我们可以使用STL中的set来表示$a$，标记方式为将其从$a$中删除，我们无需对$a$排序，因为set本来就是自动排序的。而是否出现过可以使用map来表示。总的时间复杂度大约为$O(n\log(n))$。

部分代码

set<int> a;
map<int, int> p;
vector<int> ans;

for (int i = 0; i < n; i ++) {
	int tmp;
	cin >> tmp;
	a.insert(tmp);
	p[tmp]++;
}

while (a.size()) {
	int t = *a.begin();
	ans.push_back(t);
	for (int cur = t; cur <= k; cur+=t) {
		if (!p[cur]) {
			cout << "-1\n";
			return;
		}
		auto t = a.find(cur);
		if (t != a.end()) a.erase(t);
	}
}

编辑此页

贡献者: Macro

下一页2025-12-14题目：Codeforces Round 1068 (Div. 2) B