G. Short Task - 题解

比赛与标签

比赛: Codeforces Round 713 (Div. 3) 标签: brute force, dp, math, number theory 难度: *1700

题目大意喵~

这道题呀，首先定义了一个函数 d(n)，它代表数字 n 所有正约数（包括1和它自己）的和。比如说，6的约数有1, 2, 3, 6，所以 d(6) = 1 + 2 + 3 + 6 = 12 啦。

然后呢，题目会给我们好多好多个查询，每个查询给出一个整数 c。我们的任务就是，对于每个 c，找到一个最小的整数 n，使得 d(n) = c。如果找不到这样的 n，就输出 "-1" 哦。

简单来说，就是给你一个约数和 c，让你反过来找产生这个和的最小的那个数 n，是不是很有趣呐？

解题思路喵~

直接看题目，给我们一个 c，让我们找 n，感觉像是在解一个方程 d(n) = c。可是这个 d(n) 函数长得好奇怪，直接反解 n 好像超级难的样子，喵呜~ ( ´•̥̥̥ω•̥̥̥` )

但是不要灰心！我们换个角度想一想嘛。正着来，从 n 计算 d(n) 是不是简单多啦？那我们能不能把所有可能的 (n, d(n)) 对都算出来，然后存起来，等查询 c 的时候直接找答案呢？

这个思路叫作预处理，或者叫打表！非常适合这种有很多查询，而且查询范围固定的题目哦。

具体步骤是这样哒：

确定范围：题目给的 c 最大是 10^7。因为一个数的约数和 d(n) 肯定大于等于 n 本身（至少有1和n两个约数，当n>1时），所以如果 d(n) = c，那么 n 肯定不会超过 c。所以我们只需要预处理到 10^7 就足够啦。
高效计算所有 d(n)：我们需要计算从 1 到 10^7 每个数的约数和。如果对每个数都单独分解质因数来算，那可太慢啦，会超时的说！这里有一个超级棒的技巧，类似于埃氏筛法（Sieve of Eratosthenes）的思路：
- 我们创建一个数组 d，d[i] 用来存放 i 的约数和。
- 然后我们从 i = 1 开始遍历到 10^7。对于每个 i，它会是哪些数的约数呢？当然是它自己的倍数啦！也就是 i, 2*i, 3*i, 4*i, ... 这些数。
- 所以，我们再用一个内层循环，遍历 i 的所有倍数 j（j = i, i+i, i+2i, ...），然后给 d[j] 加上 i。
- 这样两层循环跑完，d 数组里就存好了所有数字的约数和啦！这个算法的时间复杂度是 O(N log N)，非常快喵~
建立 c 到 n 的映射：现在我们有了所有 n 对应的 d(n) 值。题目要我们找的是，对于一个 c，最小的那个 n。
- 我们可以再创建一个答案数组 min_n，min_n[c] 就存放 d(n) = c 的最小 n。
- 我们从 n = 1 开始，从小到大遍历到 10^7。
- 对于每个 n，我们算出它的约数和 val = d[n]。
- 如果 val 在 10^7 范围内，并且我们还没有给 min_n[val] 赋过值（比如它还是初始的0），我们就把 n 存进去，即 min_n[val] = n。
- 因为我们是按 n 从小到大的顺序遍历的，所以第一个遇到的能使 d(n) = val 的 n，必然是最小的那个 n！之后再遇到别的 n' 也得到同样的 val，我们就不更新了，这样就保证了最小性，喵~
回答查询：预处理工作完成！现在对于每个查询 c，我们只需要看一下 min_n[c] 的值。如果它不是初始值（比如0），那就说明我们找到了答案，直接输出 min_n[c]。如果它还是初始值，就说明不存在这样的 n，输出 "-1" 就好啦。这样每次查询都是 O(1) 的，超快的说！

总结一下就是：预计算所有约数和 -> 建立反向映射 -> O(1)查询。是不是思路清晰多啦？

代码实现喵~

下面就是把我们的思路变成代码啦！咱加了详细的注释，方便大家理解每一部分都在做什么哦。

cpp

#include <iostream>
#include <vector>

using namespace std;

// c 的最大值是 10^7，所以我们预处理到这个范围就够啦
const int MAX_C = 10000000;

int main() {
    // 加速一下输入输出，让程序跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // d[i] 用来存储数字 i 的约数之和
    vector<long long> d(MAX_C + 1, 0);
    // min_n[c] 用来存储 d(n)=c 的最小的 n
    // 初始化为 0，0 在这里作为“还没找到”的标记
    vector<int> min_n(MAX_C + 1, 0);

    // 第一步：预处理计算所有数字的约数和 d(n)
    // 这个双重循环是一种类似筛法的技巧，非常高效！
    for (int i = 1; i <= MAX_C; ++i) {
        // i 是它所有倍数 j 的约数
        for (int j = i; j <= MAX_C; j += i) {
            d[j] += i; // 把 i 加到它倍数的约数和里
        }
    }

    // 第二步：建立从约数和 c 到最小 n 的映射
    // 我们从小到大遍历 n
    for (int n = 1; n <= MAX_C; ++n) {
        long long current_d = d[n]; // 当前 n 的约数和
        // 如果这个约数和在我们的处理范围内
        if (current_d <= MAX_C) {
            // 并且我们还没有为这个约数和找到过对应的 n
            if (min_n[current_d] == 0) {
                // 就把当前的 n 记录下来。因为 n 是从小到大遍历的，
                // 所以第一个找到的一定是最小的 n！
                min_n[current_d] = n;
            }
        }
    }

    // 第三步：处理所有查询
    int t;
    cin >> t;
    while (t--) {
        int c;
        cin >> c;
        // 直接在预处理好的数组里查答案，O(1) 的说！
        if (min_n[c] == 0) { // 如果是0，说明没找到对应的n
            cout << "-1\n";
        } else {
            cout << min_n[c] << '\n';
        }
    }

    return 0;
}

复杂度分析喵~

时间复杂度: O(MAX_C * log(MAX_C) + t) 的说。
- 预处理计算所有 d(n) 的部分，时间复杂度是 MAX_C/1 + MAX_C/2 + ... + MAX_C/MAX_C，这是一个调和级数，约等于 O(MAX_C * log(MAX_C))。
- 建立 min_n 映射的循环是 O(MAX_C)。
- t 次查询，每次是 O(1)。
- 所以总的时间主要花在预处理上，完全可以在规定时间内完成呐！
空间复杂度: O(MAX_C) 的说。
- 我们需要两个大小约为 MAX_C 的数组 d 和 min_n 来存储数据，所以空间复杂度和 MAX_C 是线性关系。

知识点与总结喵~

这道题真是一道非常经典的预处理打表题，让咱学到了好多东西呢！

逆向思维: 当正向求解困难时（从 c 到 n），不妨试试逆向思考（从 n 到 c），可能会发现一片新天地！
筛法思想: 计算所有数的约数和时，使用筛法思想的 O(N log N) 算法是关键，比对每个数单独计算要快得多。这是数论问题中一个非常有用的工具哦。
空间换时间: 我们通过使用额外的空间（d 和 min_n 数组）来预先存储所有可能的结果，从而将每次查询的时间从可能很高的复杂度降低到了 O(1)。这是算法竞赛中非常常见的优化策略。
细节是魔鬼: 为了找到最小的 n，在构建 min_n 映射表时，按 n 从小到大遍历并只记录第一次出现的结果，这个小细节是解题的关键之一哦！

希望这篇题解能帮助到大家！只要多思考，多练习，再难的题目也会变得像毛线球一样好玩！大家一起加油，喵~ >w<

G. Short Task - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵~ ​

代码实现喵~ ​

复杂度分析喵~ ​

知识点与总结喵~ ​