HarderGcdProblem - 题解

标签与难度

标签: 数论, 质数筛, 贪心, 构造算法, 最大匹配难度: 1800

题目大意喵~

主人你好呀~ 这道题是说，给定一个正整数 $n$ ，我们需要从集合 $\{1, 2, \dots, n\}$ 中找出两个不相交的子集 $A$ 和 $B$ 。这两个子集的大小必须相等，我们称之为 $m$ 。

最关键的条件是：集合 $A$ 中的每个元素，都能在集合 $B$ 中找到一个“好朋友”，使得它俩的最大公约数（GCD）大于 1。反之亦然，集合 $B$ 的每个元素也能在 $A$ 中找到这样的好朋友。我们要做的，就是找到一种划分方案，让这个 $m$ 尽可能地大，然后输出 $m$ 和所有配好的对，喵~

简单来说，就是把 $\{1, 2, \dots, n\}$ 里的数，尽可能多地分成一对一对的，每一对的 $\gcd$ 都要大于 1。

解题思路分析

这道题的核心在于 $\gcd(a, b) > 1$ 这个条件，它告诉我们，能配成一对的两个数 $a$ 和 $b$ 必须拥有一个共同的质因数，喵~

这启发了我们，可以从质因数的角度来思考问题！我们可以把所有数字按照它们的质因数来“分组”。比如说，所有 3 的倍数 $\{3, 6, 9, 12, \dots\}$ 就可以看作一个“3号俱乐部”，俱乐部里的任何两个成员，它们的 $\gcd$ 至少是 3，所以肯定大于 1，可以互相配对！

那么，我们应该按什么顺序来处理这些“质数俱乐部”呢？

一个很自然的想法是贪心！对于那些比较大的质数，它们的倍数在 $[1, n]$ 这个范围内会比较稀少。比如当 $n=20$ 时，质数 19 只有一个倍数 19，质数 7 也只有 7 和 14 两个倍数。这些“人丁稀少”的俱乐部，如果不优先安排，它们的成员很可能被其他俱乐部（比如“2号俱乐部”，即所有偶数）抢走，最后落单。所以，一个明智的策略是从大到小遍历质数，优先为大质数的倍数组队，喵~

那么，我们需要考虑的最大的质数是多大呢？如果一个质数 $p > n/2$ ，那么它在 $[1, n]$ 范围内的倍数只有它自己，也就是 $p$ 。它找不到另一个 $p$ 的倍数来配对，所以我们只需要考虑不大于 $n/2$ 的质数就足够啦。

好，我们的贪心策略出炉了：

从大到小遍历所有不大于 $n/2$ 的质数 $p$ 。
对于每个质数 $p$ ，找出它在 $[1, n]$ 中所有还没有被配对过的倍数。
把这些倍数两两配对。

这听起来很完美，但是有一个小小的麻烦，如果某个质数 $p$ 的未配对倍数数量是奇数个怎么办？那不就有一个数字要孤零零地落单了吗？这可不行，我们要最大化 $m$ 呀！

这个时候，我们需要一点点小智慧，喵~ 观察一下 $p$ 的倍数们： $p, 2p, 3p, 4p, \dots$ 。其中， $2p$ 这个数非常特别，因为它除了是 $p$ 的倍数，还是 2 的倍数（一个偶数）。对于一个奇质数 $p$ 来说，它的其他奇数倍（ $3p, 5p, \dots$ ）就不一定有这个“双重身份”了。

这就是破局的关键！当奇质数 $p$ 的倍数有奇数个时，我们可以暂时把 $2p$ 这个成员“请出”俱乐部。这样一来，剩下的成员数量就变成偶数啦，可以完美地两两配对！而被请出去的 $2p$ 怎么办呢？别担心，它是一个偶数，可以把它留给最后压轴出场的“2号俱乐部”，也就是所有偶数的大家庭。那里人才济济，肯定能给它找到一个伴侣的！

所以，我们最终的完美策略是这样的：

先用线性筛或者其他筛法，预处理出所有质数，这能让我们的爪子更快，喵~
创建一个 used 数组，来标记哪些数字已经被配对过了。
从不大于 $n/2$ 的最大质数开始，倒序遍历到 3。我们把质数 2 留到最后特殊处理。
对于每一个奇质数 $p$ ： a. 找出它在 $[1, n]$ 中所有未被使用的倍数，放进一个临时列表 current_multiples。 b. 如果 current_multiples 的大小是奇数，我们就从这个列表中移除 $2p$ 。 c. 将 current_multiples 中剩下的数两两配对，记录下这些配对，并把这些数标记为 used。
最后，轮到我们的“2号俱乐部”了！遍历所有在 $[1, n]$ 中还没被用过的偶数，把它们两两配对。

通过这个方法，我们就能尽可能多地凑成对，得到最大的 $m$ 啦！是不是很巧妙呢，呐？

代码实现

这是我根据上面的思路，精心为你准备的一份代码哦~ 注释很详细，希望能帮到你！

cpp

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

// 最大处理范围，根据题目设定
const int MAXN = 200005; 

// 存储质数的列表
std::vector<int> primes;
// is_prime[i] = false 表示 i 是质数
bool is_prime[MAXN];

// 使用线性筛法预处理质数，喵~
void sieve(int n) {
    std::fill(is_prime, is_prime + n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (int p : primes) {
            if ((long long)i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) break;
        }
    }
}

void solve() {
    int n;
    std::cin >> n;

    // used[i] = true 表示数字 i 已经被配对
    std::vector<bool> used(n + 1, false);
    // 存储最终的配对结果
    std::vector<std::pair<int, int>> result_pairs;

    // 找到第一个大于 n/2 的质数的位置
    auto it_start = std::upper_bound(primes.begin(), primes.end(), n / 2);

    // 从大到小遍历所有 <= n/2 的奇质数
    for (auto p_it = it_start - 1; p_it >= primes.begin(); --p_it) {
        int p = *p_it;
        if (p == 2) continue; // 2 我们最后统一处理

        // 收集所有 p 的未被使用的倍数
        std::vector<int> current_multiples;
        for (int j = p; j <= n; j += p) {
            if (!used[j]) {
                current_multiples.push_back(j);
            }
        }

        // 如果倍数数量是奇数，就暂时把 2*p 排除掉
        if (current_multiples.size() % 2 != 0) {
            int to_remove_val = 2 * p;
            // 使用 remove-erase idiom 高效删除元素
            auto remove_iter = std::remove(current_multiples.begin(), current_multiples.end(), to_remove_val);
            current_multiples.erase(remove_iter, current_multiples.end());
        }

        // 将剩下的倍数两两配对
        for (size_t i = 0; i + 1 < current_multiples.size(); i += 2) {
            result_pairs.push_back({current_multiples[i], current_multiples[i + 1]});
            used[current_multiples[i]] = true;
            used[current_multiples[i + 1]] = true;
        }
    }

    // 最后，处理所有剩下的偶数
    std::vector<int> remaining_evens;
    for (int i = 2; i <= n; i += 2) {
        if (!used[i]) {
            remaining_evens.push_back(i);
        }
    }

    // 将剩下的偶数两两配对
    for (size_t i = 0; i + 1 < remaining_evens.size(); i += 2) {
        result_pairs.push_back({remaining_evens[i], remaining_evens[i + 1]});
    }

    // 输出结果，喵~
    std::cout << result_pairs.size() << "\n";
    for (const auto& p : result_pairs) {
        std::cout << p.first << " " << p.second << "\n";
    }
}

int main() {
    // 提高输入输出效率
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 预处理质数到最大范围
    sieve(MAXN - 1);

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

    return 0;
}

复杂度分析

时间复杂度: $O(N_{max} + T \cdot n \log \log n)$
- 预处理质数的线性筛部分是 $O(N_{max})$ ，其中 $N_{max}$ 是我们筛的最大数（这里是 $2 \cdot 10^5$ ）。这部分只执行一次。
- 对于每个测试用例，我们遍历所有不大于 $n/2$ 的质数 $p$ 。对于每个 $p$ ，我们又遍历它的倍数，次数是 $n/p$ 。所有这些操作的总和近似于 $\sum_{p \le n} \frac{n}{p}$ ，这个级数约等于 $O(n \log \log n)$ 。所以每个测试用例的复杂度是 $O(n \log \log n)$ 。
空间复杂度: $O(N_{max} + n)$
- 筛法需要 $O(N_{max})$ 的空间来存储质数信息。
- 在 solve 函数中，used 数组和 result_pairs 向量都需要 $O(n)$ 的空间。所以每个测试用例需要 $O(n)$ 的额外空间。

知识点总结

这道题真是一次愉快的思维探险呢，喵~ 我们用到的知识点有：

数论基础: 解题的关键完全建立在对最大公约数（GCD）和质因数的理解上。
贪心算法: 从大到小处理质数的策略是一种贪心。我们优先满足最“苛刻”的条件（大质数的倍数少），从而为全局最优解创造了条件。
质数筛: 高效地找出所有质数是解决这类问题的基础。线性筛（欧拉筛）是非常棒的选择！
构造性思维: 题目要求我们给出一个具体的方案，而不仅仅是一个数值。我们的整个思考过程，包括如何分组、如何处理奇偶情况，都是在“构造”一个合法的解。
特殊情况处理: 识别出 $2p$ 的特殊性并加以利用，是这个贪心策略能够成功的点睛之笔，呐！

希望这篇题解能对主人有所帮助！如果还有不明白的地方，随时可以再来问我哦，喵~

HarderGcdProblem - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​