题解：CF2008G Sakurako's Task

CF2008G

我们会发现，因为需要求的是 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$ 。

因此，我们可以枚举

mex_k

具体是处于哪一个区间

[i \cdot \gcd(a_1, \dots, a_n), (i + 1) \cdot \gcd(a_1, \dots, a_n) - 1]

，然后输出即可。

CPP

#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;
}

题解：CF2008G Sakurako's Task

文章操作

CF2008G

相关推荐

评论

题解：CF2008G Sakurako's Task