题解：CF2008G Sakurako's Task

Yan719 · 2025-11-25 15:07:54 · 题解

CF2008G

我们会发现，因为需要求的是 \operatorname{mex}，所以在所有数都不同的情况下，每个数尽可能小是最优的。

由于操作是 a_i = a_i - a_j, a_i = a_i + a_j 这两种，所以我们一定可以凑出 \{0, \gcd(a_1, \dots, a_n), \dots, (n - 1) \cdot \gcd(a_1, \dots, a_n)\} 这个序列。

感性理解一下为什么可以取到 0：

就是首先我们是肯定可以取到 \gcd 的，然后，我们通过将 \gcd 和另外两个数分别进行操作，就得到了三个 \gcd。

然后对于这三个 \gcd，我们对于其中两个做一次操作就可以得到 0, \gcd, 2 \times \gcd。

因此，我们可以枚举 \operatorname{mex}_k 具体是处于哪一个区间 [i \cdot \gcd(a_1, \dots, a_n), (i + 1) \cdot \gcd(a_1, \dots, a_n) - 1]，然后输出即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int T, n, k, a[N];

int gcd(int x, int y) {
    return y ? gcd(y, x % y) : x;
}

void Solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 1) {
        cout << k - (k <= a[1]) << '\n';
        return ;
    }
    int tp = 0;
    for (int i = 1; i <= n; i++) tp = gcd(tp, a[i]);
    for (int i = 0; i < n; i++) {
        // i * tp + 1 ~ (i + 1) * tp - 1
        if (k <= tp - 1) {
            cout << i * tp + k << '\n';
            return ;
        }
        if (i < n - 1) k -= tp - 1;
    }
    cout << (n - 1) * tp + k << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> T;
    while (T--) Solve();
    return 0;
}