Moe's CF Life

Appearance

D. Coprime - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 827 (Div. 4) 标签: brute force, greedy, number theory 难度: *1100

题目大意喵~ ​

主人你好呀！这道题是这样的呐：

我们拿到一个包含 n 个正整数的数组 a。我们的任务，就是要从这个数组里找出两个元素 a[i] 和 a[j]（这里的 i 和 j 是它们在数组里的位置，从1开始数的说），需要满足这两个数是互质的。

"互质"是什么意思呢？就是说，a[i] 和 a[j] 的最大公约数（GCD）是 1 啦。比如 8 和 9 就是互质的，因为它们除了 1 之外没有其他共同的因子了喵~

在所有满足互质条件的 (i, j) 对中，我们要找到那个能让 i + j 的值变得最大的一对，然后把这个最大的和输出出来。如果整个数组里都找不到任何一对互质的数，那就要告诉裁判 -1 哦。

简单来说，就是：找互质数对，使得它们的下标之和最大！

解题思路的奇妙旅程！ ​

刚看到这道题，最朴素的想法是不是两层 for 循环，把数组里所有的数对 (a[i], a[j]) 都检查一遍呀？

cpp
// 暴力想法喵...
int max_sum = -1;
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (gcd(a[i], a[j]) == 1) {
            max_sum = max(max_sum, i + j);
        }
    }
}

但是...但是...主人你看呐，n 最大有 2 * 10^5 这么多！O(n^2) 的复杂度肯定会让程序跑到天荒地老，然后超时（TLE）的啦，呜...

这时候，就要发挥我们猫咪的敏锐观察力了喵！题面里有一个非常重要的提示：a_i 的值最大只有 1000。

n 很大，但是 a_i 的取值范围很小！这是一个经典的信号，告诉我们不要从数组的下标入手，而要从数组的值入手！

我们的思路可以来个180度大转弯：

  1. 关注值，而非下标：既然值的范围只有 [1, 1000]，我们可以遍历所有可能的值的组合 (v1, v2)，其中 1 <= v1, v2 <= 1000。
  2. 如何最大化 i+j：为了让 i + j 最大，对于一个特定的数值（比如 7），如果它在数组里出现了好几次，我们肯定要选它最后一次出现的位置（也就是最大的那个下标），对吧？这样加起来的和才有可能最大嘛！
  3. 记录最后位置：所以，我们可以先遍历一遍输入数组，用一个辅助数组 last_idx[1001] 来记录每个数值（1到1000）在原数组中最后一次出现的下标。如果一个数没出现过，它的记录就是0。
  4. 组合与检查：现在，我们就可以遍历所有可能的值 v1 (从1到1000) 和 v2 (从1到1000) 了。
    • 首先，检查 v1 和 v2 是否都在输入数组中出现过（通过 last_idx[v1] > 0 和 last_idx[v2] > 0 来判断）。
    • 如果都出现过，再检查它们是否互质 gcd(v1, v2) == 1。
    • 如果互质，那么 last_idx[v1] + last_idx[v2] 就是一个可能的答案，我们用它来更新我们的最大和 max_sum。

这样一来，我们的复杂度就从 O(n^2) 变成了 O(V^2)（V是值的最大范围，这里是1000），这已经很棒了！

还能再快一点吗喵？

当然可以！每次都计算 gcd(v1, v2) 还是有点点慢，特别是当有很多测试用例的时候。因为值的范围是固定的，哪些数对是互质的，也是固定的！我们可以预处理呀！

在所有测试用例开始之前，我们就先把 1 到 1000 之间所有互质的数对都找出来，存好。比如，我们可以用一个 vector<vector<int>> coprimes，coprimes[i] 就存着所有与 i 互质的数。

最终的完美计划是这样的说：

  1. 预处理阶段（程序开始时只做一次）：计算并存储 1 到 1000 之间所有互质的数对。
  2. 单个测试用例阶段： a. 创建 last_idx[1001] 数组，初始化为0。 b. 读入 n 和数组 a，遍历数组，填充 last_idx 数组。 c. 初始化 max_sum = -1。 d. 遍历数值 v1 从 1 到 1000： i. 如果 v1 不在数组中（last_idx[v1] == 0），就跳过。 ii. 如果 v1 在，就遍历我们预处理好的、与 v1 互质的所有数 v2。 iii. 对于每个 v2，如果它也在数组中（last_idx[v2] > 0），我们就用 last_idx[v1] + last_idx[v2] 来更新 max_sum。 e. 输出 max_sum。

这样，每个测试用例的核心部分就非常快啦！

可爱又清晰的代码实现 ​

cpp
#include <iostream>
#include <vector>
#include <numeric> // 为了 std::gcd
#include <algorithm>

// 全局预处理一个表，存储1到1000之间所有互质的数对喵~
// coprimes[i] 会存储所有 <= 1000 且与 i 互质的数 j
std::vector<std::vector<int>> coprimes(1001);

// 预处理函数，在所有测试用例开始前运行一次就够了！
void precompute_coprimes() {
    for (int i = 1; i <= 1000; ++i) {
        for (int j = i; j <= 1000; ++j) {
            // 如果 i 和 j 的最大公约数是1，它们就是互质的！
            if (std::gcd(i, j) == 1) {
                coprimes[i].push_back(j);
                // 因为是无序对，所以也要把 i 加到 j 的列表里呐
                if (i != j) {
                    coprimes[j].push_back(i);
                }
            }
        }
    }
}

void solve() {
    int n;
    std::cin >> n;
    
    // 用一个数组来记录每个数值(1-1000)最后出现的位置（1-based index）
    // 初始化为0，表示这个数还没出现过
    std::vector<int> last_idx(1001, 0);
    for (int i = 1; i <= n; ++i) {
        int val;
        std::cin >> val;
        // 更新这个数值最后出现的位置
        last_idx[val] = i;
    }

    int max_sum = -1; // 初始化最大和为-1，处理找不到的情况

    // 遍历所有可能的数值 v1 (1 到 1000)
    for (int v1 = 1; v1 <= 1000; ++v1) {
        // 如果这个数值 v1 根本没在输入数组里出现过，就直接跳过啦
        if (last_idx[v1] == 0) {
            continue;
        }
        
        // 对于存在的 v1，我们遍历所有与它互质的伙伴 v2 (这些都是预处理好的！)
        for (int v2 : coprimes[v1]) {
            // 如果这个互质伙伴 v2 也在数组里出现过...
            if (last_idx[v2] > 0) {
                // ...那么我们就找到了一个候选答案！更新最大和~
                max_sum = std::max(max_sum, last_idx[v1] + last_idx[v2]);
            }
        }
    }

    std::cout << max_sum << "\n";
}

int main() {
    // 让输入输出快如闪电喵！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 在一切开始之前，先做好预处理工作！
    precompute_coprimes();

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析时间！ ​

  • 时间复杂度: O(V^2 * logV + T * (n + V^2)) 的说

    • 预处理: precompute_coprimes 函数需要两层循环遍历 1 到 V（V=1000），每次计算 gcd 大约是 logV 的时间。所以预处理是 O(V^2 * logV)。但这只在所有测试用例开始前运行一次，所以是值得的！
    • 每个测试用例:
      • 读入数据并填充 last_idx 数组是 O(n)。
      • 之后遍历 v1 和它的互质伙伴 v2，这部分的循环次数和 n 无关，只和 V 有关。最坏情况下是 O(V^2)。
      • 所以每个测试用例的时间是 O(n + V^2)。由于 V 是个常数(1000)，而 n 是变量，我们通常会把复杂度写成 O(n)，因为它才是决定运行时间的主要因素呐。

  • 空间复杂度: O(V^2) 的说

    • coprimes 表需要存储所有互质对，空间消耗是主要部分，大致是 O(V^2) 级别。
    • last_idx 数组需要 O(V) 的空间。
    • 总的空间复杂度由 coprimes 表主导，是 O(V^2)。这也是用空间换时间的好例子哦！

知识点与总结喵~ ​

这道题真的超棒，教会了我们好多东西呢！

  1. 转换思路: 这是最重要的技巧！当问题的某个维度（如数组长度 n）非常大，而另一个维度（如元素值的范围 V）很小时，尝试从较小的维度入手，往往能发现新大陆！
  2. 预处理大法: 对于多组测试用例，如果某些计算是重复且固定的（比如本题的互质关系），一定要把它们预处理出来，可以大大提高程序效率。
  3. 空间换时间: 我们用了 last_idx 和 coprimes 这两个额外的存储空间，成功地把时间复杂度从 O(n^2) 优化到了 O(n) 级别，这是算法设计中非常常见的思想。
  4. 贪心选择: 为了让 i+j 最大，我们只保留每个数值最后出现的位置。这是一种小小的贪心策略，因为更大的下标总是有利于得到更大的和。

是不是很有趣呢？通过转换思路和一些小技巧，一个看似棘手的问题就变得简单起来了喵！继续加油，主人一定能成为算法大师的！❤️

Released under the MIT License.

Copyright © 2024-present Moe