E. Border - 题解

比赛与标签

比赛: Codeforces Round 499 (Div. 2) 标签: number theory 难度: *1800

题目大意喵~

主人 sama，欢迎来到火星喵~ 这道题是说，我们手上有 n 种面值的火星钞票，每种都有无限张。火星人使用 k 进制，并且他们有一个神秘的“神圣数字” d（0 <= d < k）。

如果咱们支付的总金额，在 k 进制下的最后一位数字恰好是 d，火星人就会非常开心！我们的任务就是，找出所有能让火星人开心的数字 d，并把它们从小到大列出来，呐。

换句话说，假设我们能凑出的总金额是 S，题目其实就是在问我们，S % k 的所有可能值是什么呢？是不是很简单呀~

解题思路大揭秘！

喵哈哈，这道题看起来有点复杂，但其实只要揭开它数论的神秘面纱，就会发现它是一只很温顺的小猫咪哦！

首先，我们来分析一下我们能凑出的总金额 S 有什么特点。我们有 n 种钞票，面值分别是 a_1, a_2, ..., a_n。我们可以用任意数量的钞票，所以总金额 S 可以表示为： S = c_1 * a_1 + c_2 * a_2 + ... + c_n * a_n 其中 c_1, c_2, ..., c_n 都是非负整数。

这里就要请出我们数论中的好朋友——裴蜀定理（Bézout's Identity） 啦！对于两个整数 a 和 b，它们的所有整数线性组合 x*a + y*b 的结果一定是 gcd(a, b) 的倍数。推广到多个整数 a_1, ..., a_n，它们的所有整数线性组合的结果，一定是 gcd(a_1, ..., a_n) 的倍数。

虽然裴蜀定理说的是整数系数，但当我们可以凑出任意大的金额时，所有能凑出的正数金额的集合，就是所有 g = gcd(a_1, a_2, ..., a_n) 的正整数倍数！所以，我们能凑出的总金额 S，一定是 g 的某个非负整数倍，即 S = m * g（其中 m >= 0）。

好啦，问题转化成：对于 S = m * g，S % k 的所有可能值是什么呢？这等价于求解 (m * g) % k 的所有可能取值。

这个问题其实是在问，在模 k 的意义下，g 的倍数能生成哪些数。根据群论或者初等数论的知识，g 在模 k 的加法群 Z_k 中生成的子群的元素，就是所有 gcd(g, k) 的倍数。

也就是说，一个数 d 能被表示成 (m * g) % k，当且仅当 d 是 gcd(g, k) 的倍数。

所以，我们的最终目标就是找出所有 gcd(g, k) 的倍数，并且这些数要小于 k。 Let's call g_final = gcd(g, k) = gcd(gcd(a_1, ..., a_n), k).

那么，所有可能的 d 就是： 0 * g_final, 1 * g_final, 2 * g_final, ... 直到这个倍数大于等于 k 为止。

这些值的数量正好是 k / g_final 个。我们只需要从 0 开始，不断地加上 g_final，就能得到所有答案啦！

总结一下步骤喵：

计算所有钞票面值的最大公约数 g0 = gcd(a_1, a_2, ..., a_n)。
计算 g = gcd(g0, k)。
可能的 d 的数量就是 k / g。
所有可能的 d 就是 0, g, 2*g, 3*g, ... 直到 k-1。

是不是一下子就清晰起来了呢，的说！

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <numeric> // C++17 中 gcd 在这里，不过手写也很简单喵~

using namespace std;

// 手写一个 gcd 函数，更加通用~
long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

    long long n, k;
    cin >> n >> k;

    // 计算所有钞票面值的最大公约数 g0
    // 一个小技巧：gcd(0, x) = x，所以 g0 初始化为 0 很方便~
    long long g0 = 0;
    for (int i = 0; i < n; i++) {
        long long val;
        cin >> val;
        g0 = gcd(g0, val);
    }

    // 根据我们的推导，最终要找的是 gcd(g0, k) 的倍数
    // g 就是我们推导中的 g_final
    long long g = gcd(g0, k);

    // 可能的 d 的数量就是 k / g
    long long count = k / g;
    cout << count << "\n";

    // 循环输出所有可能的 d
    // 它们是 0, g, 2*g, ..., (count-1)*g
    for (long long i = 0; i < count; i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << i * g;
    }
    cout << "\n";

    return 0;
}

复杂度分析的说

时间复杂度: O(N * log(A_max) + k/g) 的说。
- 我们需要计算 N 个数的最大公约数。每次 gcd 运算的复杂度大约是 O(log(A_max))，其中 A_max 是钞票的最大面值。所以这部分的复杂度是 O(N * log(A_max))。
- 之后计算 gcd(g0, k) 的复杂度是 O(log(k))。
- 最后，我们需要循环 k/g 次来输出答案。在最坏的情况下（比如 g=1），这个循环会执行 k 次。
- 所以总的时间复杂度是 O(N * log(A_max) + k/g)，在题目给定的数据范围内是完全可以通过的！
空间复杂度: O(1) 的说。
- 在我的优化版代码里，我们不需要把所有的 a_i 都存起来，可以一边读入一边计算GCD，所以只需要常数级别的额外空间。如果像题目提供的代码那样用 vector 存，空间复杂度就是 O(N) 啦，两种做法都可以AC的喵~

知识点与总结

这道题是一道非常经典的数论题，把实际问题抽象成数学模型是解题的关键呐！

核心知识点:
- 最大公约数 (GCD): 整个解法的基石。
- 裴蜀定理 (Bézout's Identity): 理解“一组数能凑出什么”的关键。它告诉我们，a 和 b 的线性组合 xa + yb 最小的正数值就是 gcd(a, b)。
- 同余理论: 将问题从无限的整数域转换到模 k 的有限集合中，是解决 ... % k 问题的标准武器。
解题技巧:
- 迭代求GCD: gcd(a, b, c) = gcd(gcd(a, b), c)，这个性质让我们能方便地求一串数的GCD。
- gcd(0, x) = x: 一个非常实用的小trick，可以简化求多个数GCD时的代码初始化。
思维总结: 当主人 sama 遇到类似“用一堆东西凑成某个目标”的问题时，可以尝试往 GCD 和 裴蜀定理 的方向思考喵~ 如果问题还带有周期性或者取模的限制，那么 同余理论 就会是你的好帮手！

希望这篇题解能帮助到你，如果还有问题，随时可以再来问我哦！喵~

E. Border - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​