Moe's CF Life

Appearance

G. Sakurako's Task - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 970 (Div. 3) 标签: binary search, greedy, math, number theory 难度: *1800

樱子的小任务是什么喵？ - 题目大意 ​

午安喵~ 主人！樱子酱给我们准备了一个有趣的数组挑战哦！(ฅ'ω'ฅ)

是这样的呐：我们有一个包含 n 个整数的数组 a。我们可以进行一种神奇的操作：选择两个不同的下标 i 和 j，并且要满足 a[i] >= a[j]。然后，我们可以把 a[i] 变成 a[i] - a[j] 或者 a[i] + a[j]。这个操作可以进行任意多次哦！

我们的目标是，通过这些操作，让数组的 mex_k 值变得尽可能大！

欸？mex_k 是什么意思喵？它指的是，在所有非负整数中，第 k 个没有出现在数组里的数。 举个栗子：

  • 如果数组是 {1, 2, 3}，那么没出现的数有 0, 4, 5, ...。第一个 (mex_1) 没出现的数就是 0。
  • 如果数组是 {0, 2, 4}，那么没出现的数有 1, 3, 5, ...。第二个 (mex_2) 没出现的数就是 3。

简单来说，就是要我们通过操作，让前 k-1 个“空位”被尽可能大的数占据，从而把第 k 个“空位”推到更大的值上，的说！

猫娘的解题思路全解析！ ​

哼哼~ 这个问题看起来有点复杂，但只要跟紧本猫娘的思路，一切都会变得清晰起来的，喵！🐾

第一步：看穿操作的本质喵！ ​

a[i] = a[i] - a[j] 和 a[i] = a[i] + a[j]... 这两个操作是不是很眼熟呀？它们是欧几里得算法（辗转相除法）的核心部件！

根据一个非常重要的数论知识——裴蜀定理（Bézout's identity），对于一组不全为零的整数 a_1, a_2, ..., a_n，我们通过反复的加减操作，最终能表示出来的所有数的集合，恰好是它们最大公约数 g = gcd(a_1, a_2, ..., a_n) 的所有倍数！

也就是说，无论我们怎么操作，数组里的所有元素最终都会变成 g 的倍数。而且，只要 n > 1，我们甚至可以造出 0（比如让两个数相等，然后相减），以及任何非负的 g 的倍数（只要数组里有足够的空间）。

第二步：如何最大化 mex_k 呢？ ​

要让第 k 个没出现的数（mex_k）变得最大，我们应该怎么做呢？

答案是：让前面出现的数字尽可能小，尽可能地“紧凑”！这样就能把“空位”推到很后面去。

既然我们只能生成 g 的倍数，那么为了让数组中的数尽可能小，最理想的情况就是把数组变成 {0, g, 2g, 3g, ..., (n-1)g}。这是我们能构造出的包含 n 个不同非负整数的、最“紧凑”的 g 的倍数集合了。

所以，问题就转化成了：假设我们的数组变成了 {0, g, 2g, ..., (n-1)g}，求这个新数组的 mex_k 是多少？

第三步：在新数组里找 mex_k！ ​

现在我们的数组是 {0, g, 2g, ..., (n-1)g}。我们来分析一下哪些数字“没出现”：

  1. 所有不是 g 的倍数的数。
  2. 所有大于等于 ng 的、是 g 的倍数的数。

接下来，我们就要分情况讨论啦，喵~

特殊情况：n = 1 ​

如果只有一个数，我们什么操作都做不了，数组是固定的 {a[0]}。

  • 没出现的数是 0, 1, ..., a[0]-1 （共 a[0] 个）和 a[0]+1, a[0]+2, ...
  • 如果 k <= a[0]，那么第 k 个没出现的数就是 k-1。
  • 如果 k > a[0]，前 a[0] 个没出现的数是 0 到 a[0]-1。我们需要找这之后的第 k - a[0] 个没出现的数。这个序列是 a[0]+1, a[0]+2, ...，第 j 项是 a[0]+j。所以我们要找的数是 a[0] + (k - a[0]) = k。

一般情况：n > 1 ​

首先，我们计算出所有输入数字的 g = gcd(a_1, ..., a_n)。

1. 如果 g = 1: 这意味着我们可以生成任何非负整数！最理想的数组就是 {0, 1, 2, ..., n-1}。

  • 没出现的数是 n, n+1, n+2, ...。
  • 第 k 个没出现的数就是 n + (k-1)。

2. 如果 g > 1: 我们的理想数组是 {0, g, 2g, ..., (n-1)g}。

  • 我们先数一数，在 ng 之前有多少个没出现的数。
  • 在 [0, ng-1] 这个区间里，总共有 ng 个整数。其中有 n 个数 (0, g, ..., (n-1)g) 出现在了数组里。
  • 所以，小于 ng 的没出现的数有 ng - n = n * (g-1) 个。我们把这个数量记作 C_main。
  • 当 k <= C_main 时: 这说明我们要找的第 k 个没出现的数，它是一个小于 ng 的、不是 g 的倍数的数。 我们要找第 k 个不是 g 的倍数的数。这里有一个神奇的公式喵！答案是 k + floor((k-1) / (g-1))。 为什么呢？可以这样想，每 g 个数里，有 g-1 个不是 g 的倍数。所以第 k 个非 g 的倍数，大概在 k * g/(g-1) 附近。这个公式 k + floor((k-1)/(g-1)) 就是对这个思想的精确计算，主人可以自己推导一下，很有趣的哦！
  • 当 k > C_main 时: 这说明我们要找的数已经超出了 ng 的范围。 前 C_main 个没出现的数，是那些小于 ng 的非 g 的倍数。 从 ng 开始，所有的整数 ng, ng+1, ng+2, ... 都没有出现在我们的理想数组里。 所以，第 C_main + 1 个没出现的数是 ng。 第 C_main + 2 个没出现的数是 ng + 1。 ... 第 C_main + j 个没出现的数是 ng + j - 1。 我们正在找第 k 个，所以令 j = k - C_main。 代入公式，答案就是 ng + (k - C_main) - 1。

好啦！把这些情况组合起来，就能解决问题了！是不是感觉豁然开朗了呢？(>ω<)

听话的代码实现喵~ ​

cpp
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 处理一个测试用例的说
void solve() {
    long long n;
    long long k;
    std::cin >> n >> k;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 特殊情况：当 n=1 时，无法进行任何操作，数组是固定的喵
    if (n == 1) {
        // 没出现的数是 0, 1, ..., a[0]-1, a[0]+1, ...
        // 如果 k 小于等于 a[0]，那么第 k 个没出现的数就是 k-1
        if (k <= a[0]) {
            std::cout << k - 1 << "\n";
        } else {
            // 如果 k 大于 a[0]，那么第 k 个没出现的数就是 k 本身
            std::cout << k << "\n";
        }
        return;
    }

    // 一般情况：当 n > 1 时，我们能生成的数都是 gcd 的倍数
    // 先计算所有数的最大公约数 g
    long long g = 0;
    if (n > 0) {
        g = a[0];
        for (int i = 1; i < n; ++i) {
            g = std::gcd(g, a[i]);
        }
    }

    // 为了最大化 mex_k，我们贪心地用最小的 g 的倍数填充数组
    // 理想的数组是 {0, g, 2g, ..., (n-1)g}

    // 如果 g=1，我们可以生成任何非负整数
    if (g == 1) {
        // 理想数组是 {0, 1, ..., n-1}
        // 没出现的数从 n 开始，第 k 个就是 n + k - 1
        std::cout << n + k - 1 << "\n";
        return;
    }

    // 如果 g > 1:
    // 理想数组是 {0, g, 2g, ..., (n-1)g}
    // 没出现的数分为两种：小于 ng 的非 g 的倍数，和大于等于 ng 的所有数

    // 首先计算小于 ng 的没出现的数的总数 C_main
    // 在 [0, ng-1] 区间里，有 n 个 g 的倍数，所以有 ng - n 个非 g 的倍数
    long long C_main = n * (g - 1);

    if (k <= C_main) {
        // 如果 k 在这个范围内，说明我们要找的 mex_k 是一个小于 ng 的非 g 的倍数
        // 我们要找第 k 个不是 g 的倍数的数
        // 这里有个很棒的公式可以直接计算！
        long long q = (k - 1) / (g - 1);
        long long ans = k + q;
        std::cout << ans << "\n";
    } else {
        // 如果 k 超出了这个范围，说明 mex_k 大于等于 ng
        // 前 C_main 个没出现的数已经填满了小于 ng 的所有“空位”
        // 第 (C_main + 1) 个没出现的数是 ng
        // 第 (C_main + j) 个没出现的数是 ng + j - 1
        // 我们要找第 k 个，所以 j = k - C_main
        long long ans = n * g + (k - C_main - 1);
        std::cout << ans << "\n";
    }
}

int main() {
    // 加速输入输出，让程序跑得飞快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析时间！ ​

  • 时间复杂度: O(N * log(max(a_i))) 的说。对于每个测试用例，我们最耗时的操作是遍历数组一次来计算所有元素的最大公约数。std::gcd(a, b) 的复杂度大约是 O(log(min(a, b)))。所以总的时间复杂度就是 O(n * logA)，其中 A 是数组中的最大值。因为所有测试用例的 n 的总和有上限，所以这个速度是完全没问题的！
  • 空间复杂度: O(N) 的说。我们主要需要一个大小为 n 的向量来存储输入的数组，所以空间开销是线性的。

知识点与总结喵~ ​

这次的挑战真是收获满满呢！让本猫娘来总结一下吧：

  1. 核心数论知识: 这道题的突破口在于理解加减运算和**最大公约数(GCD)**的关系。能够意识到所有可生成的数都是 gcd 的倍数，是解题的关键一步。这是裴蜀定理的一个漂亮应用！
  2. 贪心策略: 为了最大化 mex_k，我们采取了贪心思想。用最小的、最密集的合法数字（即 {0, g, 2g, ...}）来填充数组，从而将“空位”推到尽可能大的位置。
  3. 细致的分类讨论: 确定了理想数组后，问题就变成了计数问题。我们需要根据 g 的值（g=1 或 g>1）以及 k 和“空位数” C_main 的关系进行分类讨论，每种情况都有不同的计算方法。
  4. 神奇的计数公式: ans = k + floor((k-1)/(g-1)) 这个公式是寻找第 k 个非 g 的倍数的利器，记住它可以在遇到类似问题时派上大用场哦！
  5. 边界处理: 不要忘记 n=1 这种无法操作的特殊情况，它需要单独处理。

总而言之，这是一道将数论、贪心和细致的计数分析巧妙结合在一起的好题！希望我的题解能帮助到你，主人要继续加油哦！喵~ ( ´ ▽ ` )ﾉ

Released under the MIT License.

Copyright © 2024-present Moe