题解：CF2167D Yet Another Array Problem

tssys · 2025-11-21 10:50:54 · 题解

思考

不难注意到，若想选择一个最小的数 x(x>1)，使得这一个数与集合 \{a_i\}(a_i>1) 中的所有数字互质，那么 x 一定是质数，所以我们枚举所有质数一一判断是否满足条件，我们可以转化为证明这个问题。

设 A = \{a_1, a_2, \dots, a_n\} 是一个集合，其中每个 a_i > 1。

选择最小的 x(x > 1)，使得

证明这样的 x 一定是质数。

证明

我们考虑使用反证法。假设 x 不是质数，则 x 为合数。

由于 x > 1 且为合数，x 至少有一个质因数 p(p > 1)，满足 p \mid x 且 p \leq x/2 < x。

由于 x 与所有 a_i 互质，即 \gcd(x, a_i) = 1 对所有 a_i 成立。

我们考虑质因数 p：

如果存在某个 a_i 使得 \gcd(p, a_i) > 1，则由于 p 是质数，有 p \mid a_i。

又因为 p \mid x，可得 p \mid \gcd(x, a_i)，从而 \gcd(x, a_i) \geq p > 1。 这与 \gcd(x, a_i) = 1 矛盾。

因此，p 必须与所有 a_i 互质，即 \gcd(p, a_i) = 1 对所有 a_i 成立。

但 p < x 且 p > 1，这与 x 是满足条件的最小整数矛盾。

故假设不成立，x 必为质数。

故所以我们枚举所有质数是正确的。