G. 樱子的任务 - 详细题解

问题重述

给定一个长度为 $n$ 的数组 $a$，允许进行操作：选择 $i \neq j$ 且 $a_i \ge a_j$，将 $a_i$ 替换为 $a_i - a_j$ 或 $a_i + a_j$。求经过任意次操作后，$\operatorname{mex}_k$ 的最大可能值。

其中 $\operatorname{mex}_k$ 表示数组中缺失的第 $k$ 个非负整数。

---

关键观察

观察 1：$n = 1$ 的情况

当 $n = 1$ 时，无法进行任何操作（因为需要两个不同的下标），数组无法改变。

因此，$\operatorname{mex}_k$ 就是原数组的 $\operatorname{mex}_k$。

---

观察 2：$n > 1$ 时的数论性质

设 $g = \gcd(a_1, a_2, \dots, a_n)$。

根据数论知识，通过反复执行 $a_i = a_i \pm a_j$ 的操作（类似于辗转相除法），我们可以生成所有 $g$ 的倍数，并且只能生成 $g$ 的倍数。

重要结论：

• 我们可以将任意元素变为 $0$
• 我们可以生成任意 $g$ 的倍数（包括负数和正数）
• 由于操作要求 $a_i \ge a_j$，我们实际上只能生成非负数

最优策略：将数组变为最小的 $n$ 个 $g$ 的倍数，即：

$$0, g, 2g, 3g, \dots, (n-1)g$$

这样可以让最小的非负整数尽可能密集地覆盖，从而最大化 $\operatorname{mex}_k$。

---

观察 3：为什么是最优的？

• 数组中的数只能是 $g$ 的倍数
• 要最大化第 $k$ 个缺失的数，我们希望数组尽可能密集地覆盖从小到大的数
• 最优方案就是取最小的 $n$ 个非负 $g$ 的倍数：$0, g, 2g, \dots, (n-1)g$

---

问题转化

设最优数组为：

$$b_i = (i-1) \cdot g, \quad i = 1, 2, \dots, n$$

我们需要找到这个数组的 $\operatorname{mex}_k$。

---

计算 $\operatorname{mex}_k$

方法

设 $lst$ 为当前已经考虑的最后一个数，初始 $lst = -1$。

遍历数组 $b$（包括一个虚拟的无穷大结尾），对于每个 $b_i$：

• 区间 $(lst, b_i)$ 中的整数都是缺失的
• 区间长度为 $b_i - lst - 1$
• 如果 $k \le$ 区间长度，则答案在区间内，输出 $lst + k$
• 否则，$k$ 减去区间长度，$lst$ 更新为 $b_i$，继续

---

算法步骤

1. 读入 $n, k$ 和数组 $a$
2. 如果 $n = 1$：
   • 直接输出 $k$（因为只有一个数，第 $k$ 个缺失的就是 $k-1$？需要验证）
   • 实际上当 $n=1$ 时，数组只有一个数 $a_1$，缺失的数依次为 $0,1,2,\dots$（跳过 $a_1$）
   • 如果 $a_1 \ge k$，则 $\operatorname{mex}_k = k-1$；否则 $\operatorname{mex}_k = k$
   • 标程中用 $g=0$ 的情况处理，输出 $k$
3. 计算 $g = \gcd(a_1, a_2, \dots, a_n)$
4. 构造最优数组 $b_i = (i-1) \cdot g$
5. 遍历 $b$，计算 $\operatorname{mex}_k$

---

完整代码

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, k;
        cin >> n >> k;
        
        vector<long long> a(n);
        long long g = 0, mx = 0;
        
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            g = __gcd(g, a[i]);
            mx = max(mx, a[i]);
        }
        
        // n = 1 的情况
        if (g == 0) {
            cout << k << "\n";
            continue;
        }
        
        // 构造最优数组: 0, g, 2g, ..., (n-1)g
        sort(a.begin(), a.end());
        
        long long q = -g;
        for (int i = 0; i < n; i++) {
            q += g;
            a[i] = q;
        }
        
        // 添加虚拟结尾
        a.push_back(1e16);
        
        long long lst = -1;
        for (int i = 0; i <= n; i++) {
            if (k <= a[i] - lst - 1) {
                break;
            }
            k -= max(a[i] - lst - 1, 0LL);
            lst = a[i];
        }
        
        cout << lst + k << "\n";
    }
    
    return 0;
}

---

算法图解

以样例 n=4, k=5, a=[2,2,2,16] 为例：

1. 计算 $g = \gcd(2,2,2,16) = 2$
2. 最优数组：$[0, 2, 4, 6]$
3. 计算 $\operatorname{mex}_5$：

区间	缺失数	累计缺失	k=5
(-1, 0)	长度 0	0	k=5
(0, 2)	缺失 {1}	1	k=4
(2, 4)	缺失 {3}	2	k=3
(4, 6)	缺失 {5}	3	k=2
(6, ∞)	缺失 {7,8,9,...}	-

当遍历到区间 $(4,6)$ 时，$k=3 >$ 区间长度 $1$，继续：

• $k = 3 - 1 = 2$
• $lst = 6$

然后进入区间 $(6, \infty)$，此时 $k=2 \le$ 无穷大，答案 $= lst + k = 6 + 2 = 8$

输出：$8$ ✓

---

时间复杂度

• 计算 gcd：$O(n \log M)$
• 排序：$O(n \log n)$
• 遍历：$O(n)$
• 总复杂度：$O(n \log n)$ 每个测试用例

---

示例验证

$n$	$k$	$a$	$g$	最优数组	$\operatorname{mex}_k$	输出
1	3	[3]	0	-	$k=3$	3
2	10	[1,1]	1	[0,1]	第10个缺失：11	11
3	1	[1,2,3]		[0,1,2]	第1个缺失：3	3
	2	[1,2,4]			第2个缺失：4	4
4	5	[2,2,2,16]	2	[0,2,4,6]	第5个缺失：8	8
		[2,2,2,3]	1	[0,1,2,3]

与样例输出完全一致。

---

关键公式总结

$$\boxed{\text{最优数组} = [0, g, 2g, 3g, \dots, (n-1)g]} $$$$\boxed{\operatorname{mex}_k = \text{第 } k \text{ 个不在该数组中的非负整数}} $$

其中 $g = \gcd(a_1, a_2, \dots, a_n)$。