H. GCD 更大 详细题解

题目核心理解

给定长度为 $n$ 的数组 $a$ 和整数 $x$，需要将数组分成两组：

• 红色组：选取 $2$ ~ $n-2$ 个数，计算它们的最大公约数 $\gcd$。
• 蓝色组：剩下所有数，计算它们的按位与 $\operatorname{AND}$ 并加上 $x$。

要求满足：

$$\gcd(\text{红色数字}) > \operatorname{AND}(\text{蓝色数字}) + x $$

输出任意一组方案，无解则输出 $\text{NO}$。

---

核心思路

1. 关键性质

• 最优策略只需要选 2 个数字作为红色组。选取更多数字不会让 $\gcd$ 更大，反而会让蓝色组数字变少、按位与更大，对更严格条件。
• 把一个数从红色组移到蓝色组：$\gcd$ 不会减小，按位与不会增大。
• 设整个数组的按位与为 $A$，则只需寻找满足 $\gcd > A + x$ 的数对。

2. 位与筛选规则

• 如果某一位 $y$ 在超过 2 个数中是 $0$，则所有数的按位与这一位一定为 $0$。
• 只在不超过 2 个数中为 $0$ 的位需要重点保留，这些数是候选红色数。

3. 枚举检查规则

1. 预处理全数组按位与 $A$，目标下界为 $A+x+1$。
2. 从下界到 $\max(a_i)$ 枚举可能的 $\gcd$ 值。
3. 检查数组中是否存在一对数都能被该值整除。
4. 存在则直接输出这对数为红色组，其余为蓝色组。

---

算法流程

1. 读入 $n, x$ 与数组 $a$。
2. 计算整个数组的按位与 $A$。
3. 设定目标阈值：$limit = A + x$。
4. 枚举前若干个数（约 60 个）的两两组合：
   • 计算两数的 $\gcd$。
   • 若 $\gcd > limit$，输出方案并结束。
5. 若遍历完无满足条件数对，输出 $\text{NO}$。

---

公式与复杂度分析

核心判定条件：

$$\gcd(a_i,a_j) > \left(\operatorname{AND}_{k=1}^n a_k\right) + x $$

复杂度

• 全数组按位与：$O(n)$
• 枚举数对：$O(\log \max A \cdot n)$
• 总时间复杂度：$O(n \cdot \log \max A)$

可轻松处理 $n \le 4\times10^5$、多组数据总和限制。