[D. Array and GCD] - 题解

比赛与标签

比赛: Educational Codeforces Round 178 (Rated for Div. 2) 标签: binary search, greedy, math, number theory 难度: *1400

题目大意喵~

主人们好喵~！这道题是说，我们有一个整数数组 a。我们可以进行两种操作：

花 1 个金币，把数组里任意一个数加 1。
把数组里任意一个数减 1，然后得到 1 个金币。

一个数组被称为 理想数组，需要同时满足两个条件：

所有元素都大于等于 2。
任意两个不同的元素，它们的最大公约数 (GCD) 都必须是 1（也就是它们俩互质）。

一个数组被称为 美丽数组，如果它可以在我们初始没有金币的情况下，通过上面的操作变成一个理想数组。也就是说，我们通过减法操作得到的金币，要足够支付加法操作花的金币，喵~

我们的任务是，从给定的数组 a 中，移除最少数量的元素，使得剩下的数组是一个 美丽数组。当然，我们也可以一个都不移除，或者把整个数组都移除了，的说。

思路分析喵~

这个问题看起来有点绕，又是理想数组又是美丽数组的，但别担心呐，跟着本喵的思路一步步来，很快就能搞定的说！我们的目标是移除最少的元素，这其实就等价于，找到最多能保留多少个元素，让它们组成一个美丽数组，对吧喵？

核心思想: 咱们的核心任务是把复杂的“美丽”条件，转化成一个简单明了的数学关系。然后用贪心的策略，找出能满足这个关系的最大子集，的说。
关键观察:
- “美丽”的本质是什么喵？ 假设我们决定保留 k 个元素，组成了一个新数组 b。我们要把它变成一个理想数组 b'。美丽数组的条件是“得到的金币 >= 花费的金币”。
  - 花费的金币 = 所有 b'_i > b_i 的 (b'_i - b_i) 的总和。
  - 得到的金币 = 所有 b_i > b'_i 的 (b_i - b'_i) 的总和。所以条件就是： sum(b_i - b'_i) 对于所有 b_i > b'_i 的项 >= sum(b'_i - b_i) 对于所有 b'_i > b_i 的项。把这个不等式整理一下，会惊奇地发现它等价于一个非常简单的形式：sum(b_i) >= sum(b'_i)！也就是说，我们保留的这 k 个元素的总和，必须大于等于我们想变成的那个理想数组 b' 的元素总和，呐。
- 如何让 sum(b') 最小化呢？ 为了让 sum(b) >= sum(b') 这个条件更容易被满足，我们当然希望目标理想数组 b' 的总和 sum(b') 越小越好。一个大小为 k 的理想数组，所有元素都 >= 2 并且两两互质。要想让它们的和最小，我们应该选择最小的 k 个满足这些条件的数。那会是什么呢？当然是最小的 k 个素数啦（比如 k=3 时，就是 2, 3, 5）！所以，大小为 k 的理想数组的最小可能总和，就是前 k 个素数的和。我们把它记作 S_p(k)。
- 如何让 sum(b) 最大化呢？ 现在问题变成了：我们要从原数组 a 中选出 k 个元素，让它们的和 sum(b) 尽可能大，这样才更有可能满足 sum(b) >= S_p(k)。这是一个非常经典的贪心选择！要想让 k 个元素的和最大，我们当然是选原数组 a 中那 k 个最大的元素啦，的说。
算法流程: 把这些观察组合起来，我们的算法就清晰多啦，喵~
1. 预处理素数前缀和: 我们需要 S_p(k) 的值。因为 n 最大是 4 * 10^5，所以我们最多可能需要前 4 * 10^5 个素数的和。我们可以用“埃氏筛法”预处理出素数，然后计算出它们的前缀和，存在一个数组 P 里，P[k] 就表示前 k 个素数的和。
2. 处理输入: 对于每个测试用例，读入 n 和数组 a。
3. 贪心选择: 为了方便地取到前 k 大的元素，我们先把数组 a 从大到小 排序。
4. 计算前缀和: 对排好序的数组 a 计算前缀和 prefix，这样 prefix[k] 就代表了 a 中前 k 大元素的和。
5. 寻找最大的 k: 我们从 k=1 循环到 n，检查 prefix[k] >= P[k] 是否成立。我们记录下所有满足这个条件里，最大的那个 k，记为 max_k。
6. 输出结果: 我们最多能保留 max_k 个元素。那么最少需要移除的元素数量就是 n - max_k。搞定收工，的说喵！

代码实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

// 我们最多需要前 400000 个素数
const int MAX_K = 400000;
// 第 400000 个素数大概在 6*10^6 附近，所以筛到这个数足够了
const int LIM = 6000000; 

// P[k] 用来存储前 k 个素数的和
vector<long long> P(MAX_K + 1, 0);

// 预处理函数，用埃氏筛法找出素数并计算前缀和
void precompute_primes() {
    vector<bool> is_prime(LIM + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= LIM; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            // 只要找到足够多的素数就停下来，喵~
            if (primes.size() >= MAX_K)
                break;
            // 经典的筛法优化
            if ((long long)i * i <= LIM) {
                for (long long j = (long long)i * i; j <= LIM; j += i) {
                    is_prime[j] = false;
                }
            }
        }
    }
    
    // 计算素数的前缀和
    P[0] = 0;
    for (int k = 1; k <= MAX_K; k++) {
        P[k] = P[k - 1] + primes[k - 1];
    }
}

int main() {
    // 加速输入输出，是个好习惯喵~
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    // 在所有测试用例开始前，先做一次预处理
    precompute_primes();

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // 为了贪心地选取最大的k个元素，我们先把数组从大到小排个序，的说。
        sort(a.rbegin(), a.rend());

        // 计算排序后数组的前缀和，这样就能O(1)得到前k大元素的和啦。
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + a[i];
        }

        int max_k = 0;
        // 遍历所有可能的 k (保留的元素数量)
        for (int k = 1; k <= n; k++) {
            // 如果 k 超出了我们预处理的范围，就不用再试了
            if (k > MAX_K) {
                break;
            }
            // 这是我们推导出的核心判断条件！
            // 检查当前k个最大元素的和，是否足够支付变成前k个素数的“成本”。
            if (prefix[k] >= P[k]) {
                max_k = k; // 如果满足，就更新我们能保留的最大数量
            }
        }
        
        // 最终答案就是总数n减去我们能保留的最大数量max_k，喵！
        cout << n - max_k << '\n';
    }

    return 0;
}

复杂度分析

时间复杂度: O(LIM * log(log(LIM)) + ΣN * logN) 的说。预处理素数筛法的时间复杂度大约是 O(LIM * log(log(LIM)))，其中 LIM 是我们筛到的上界。这部分是一次性的。对于每个测试用例，主要的时间开销在于对数组 a 进行排序，即 O(N log N)。因为所有测试用例的 N 加起来有上限，所以总时间是完全可以接受的，的说。
空间复杂度: O(LIM + MAX_K) 的说。我们主要需要空间来存储埃氏筛用的 is_prime 数组（大小为 LIM），以及素数前缀和数组 P（大小为 MAX_K）。每个测试用例中的数组 a 可以复用空间。

知识点总结

解决这个问题，我们主要用到了这些可爱的知识点，方便大家复习，的说喵~

贪心算法 (Greedy Algorithm): 为了让和最大/最小，我们总是做出当前看起来最优的选择。
数论 (Number Theory): 理解了互质和素数的概念，是找到最小理想和的关键。
埃氏筛法 (Sieve of Eratosthenes): 一种高效预处理素数的方法。
前缀和 (Prefix Sums): 快速计算任意区间和的利器，这里用来快速得到前 k 大元素的和。

[D. Array and GCD] - 题解 ​

比赛与标签 ​

题目大意喵~ ​

思路分析喵~ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​