Moe's CF Life

喵~ 主人，你好呀！今天由我，你最可爱的小猫娘，来为你讲解一道非常有趣的数论问题——Codeforces 1458A - Row GCD。

别看这道题的数字都好大好大的，可能会吓到一些人，但其实只要发现其中暗藏的数学小魔法，问题就会变得像猫咪的毛线球一样，轻轻一拉就解开啦！那么，就让本猫娘带你一步步揭开它的神秘面纱吧，喵~

题目大意

这道题是这样哒：

题目会给我们两个正整数序列，一个叫做 a，长度是 n；另一个叫做 b，长度是 m。

对于 b 序列中的 每一个 元素 b_j，我们都需要计算一个值。这个值是什么呢？就是把 b_j 和 a 序列中的 每一个 元素 a_i 分别相加，得到一个新的序列 (a_1 + b_j, a_2 + b_j, ..., a_n + b_j)。然后，我们要计算这个新序列里所有数字的 最大公约数 (GCD)。

最后，把对每个 b_j 计算出的结果，依次输出就可以啦。

举个例子哦：假设 a = {1, 25, 121, 169}，b = {1, 2, 7, 23}。

当 b_j = 1 时，我们要计算 GCD(1+1, 25+1, 121+1, 169+1)，也就是 GCD(2, 26, 122, 170)，结果是 2。
当 b_j = 2 时，我们要计算 GCD(1+2, 25+2, 121+2, 169+2)，也就是 GCD(3, 27, 123, 171)，结果是 3。
... 以此类推。

解题思路

如果看到题目就直接上手，对于每一个 b_j，都去遍历整个 a 序列来计算 GCD，那可就太慢啦，喵呜... n 和 m 的最大值可是 2 * 10^5 呢，O(m * n * log(A)) 的复杂度肯定会超时的。

所以，我们需要更聪明的办法！这时候，就要请出我们数论中的一个重要性质啦：

GCD 的性质：GCD(x, y) = GCD(x, y - x)

这个性质告诉我们，两个数的最大公约数，等于其中一个数与它们差的最大公约数。这个性质可以推广到多个数哦：

GCD(x_1, x_2, ..., x_n) = GCD(x_1, x_2 - x_1, x_3 - x_1, ..., x_n - x_1)

这个性质简直就是为我们这道题量身定做的魔法呀！让我们把它应用到题目中：

我们要计算 GCD(a_1 + b_j, a_2 + b_j, ..., a_n + b_j)

根据上面的性质，我们可以把每一项（从第二项开始）都减去第一项 (a_1 + b_j)：

= GCD(a_1 + b_j, (a_2 + b_j) - (a_1 + b_j), ..., (a_n + b_j) - (a_1 + b_j))

化简一下括号里的内容：

= GCD(a_1 + b_j, a_2 - a_1, ..., a_n - a_1)

锵锵！主人请看！神奇的事情发生了！

后面那一长串 (a_2 - a_1, ..., a_n - a_1) 根本就和 b_j 没有关系了呀！这意味着，无论 b_j 取什么值，这一部分都是固定不变的。

所以，我们的策略就非常清晰啦：

预处理：我们先计算出后面这一长串不变量的最大公约数。令 g = GCD(a_2 - a_1, a_3 - a_1, ..., a_n - a_1)。因为 a_i - a_1 可能是负数，而 GCD 通常在正整数上定义，所以我们要取它们的绝对值，即 g = GCD(|a_2 - a_1|, |a_3 - a_1|, ..., |a_n - a_1|)。
计算答案：对于每一个 b_j，我们要求的答案就简化成了 GCD(a_1 + b_j, g)。这个计算就非常快啦！

这样，我们只需要一次遍历来计算 g，然后 m 次简单的 GCD 计算。总的复杂度大约是 O(n*log(A) + m*log(A))，完全可以通过啦！

小细节喵~

如果 n = 1 怎么办？那 g 怎么算呢？我们的代码里可以将 g 初始化为 0。因为 GCD(x, 0) = |x|，所以当 n=1 时，g 保持为 0，最后的答案就是 GCD(a_1 + b_j, 0) = a_1 + b_j，这是正确的！
题目中的数字最大到 10^18，所以要用 long long 类型来存储哦。

题解代码

这是带有本猫娘注释的 C++ 代码实现哦，希望能帮助主人更好地理解！

cpp

#include <iostream>
#include <vector>
#include <numeric> // std::gcd 在这里面喵
#include <cmath>   // std::abs 在这里面喵

// 解决问题的主函数~
void solve() {
    // 读取 n 和 m 的大小，喵~
    int n;
    int m;
    std::cin >> n >> m;

    // 读取序列 a。数字很大，要用 long long 哦！
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 这里就是魔法发生的地方！
    // 我们要计算 GCD(a_1+b_j, a_2-a_1, ..., a_n-a_1)
    // 所以先预处理出 g = GCD(a_2-a_1, a_3-a_1, ...)
    // 注意要取差的绝对值哦！
    
    // g 初始化为 0，这样 n=1 的时候也能正确处理啦。
    // 因为 GCD(x, 0) = |x|，非常方便！
    long long g = 0;
    if (n > 1) { // 只有 n > 1 时，才有 a_i - a_0 这一说
        for (int i = 1; i < n; ++i) {
            g = std::gcd(g, std::abs(a[i] - a[0]));
        }
    }
    
    // 现在，对于每一个 b_j，答案就是 GCD(a_1 + b_j, g)
    // 循环 m 次，依次计算并输出结果
    for (int j = 0; j < m; ++j) {
        long long b_j;
        std::cin >> b_j;
        
        // 计算最终结果
        long long result = std::gcd(a[0] + b_j, g);
        
        // 输出结果，注意最后一个数字后面没有空格哦
        std::cout << result << (j == m - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    // 加速一下输入输出，不然数据量大了会慢吞吞的
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}

知识点介绍

这道题主要用到了关于最大公约数（GCD）的一些知识，本猫娘来给你梳理一下吧！

最大公约数 (Greatest Common Divisor, GCD)
- 定义：几个整数中，能够同时整除它们所有数的那个最大的正整数，就是它们的最大公约数。比如 GCD(12, 18) 就是 6。
- 计算方法：最经典和高效的方法是 欧几里得算法（辗转相除法）。它的核心是 gcd(a, b) = gcd(b, a % b)，直到其中一个数为 0，另一个数就是答案。C++ 的 <numeric> 库里直接提供了 std::gcd 函数，非常方便。
GCD 的重要性质
- 核心性质：gcd(a, b) = gcd(a, b - a) 或 gcd(a, b) = gcd(b, a - b)
  - 这个是本题解法的基石！为什么成立呢？喵~ 假设 d 是 a 和 b 的一个公约数，那么 a = k1*d, b = k2*d。于是 b - a = (k2 - k1) * d，所以 d 也是 a 和 b-a 的公约数。反之亦然。所以它们的公约数集合完全相同，最大公约数自然也相同啦！
- 结合律：gcd(a, b, c) = gcd(a, gcd(b, c))
  - 这个性质让我们在求多个数的 GCD 时，可以两两计算，不断迭代。我们的代码 g = std::gcd(g, ...) 就是利用了这一点。
- 与 0 的关系：gcd(a, 0) = |a|
  - 任何非零整数都能整除 0，所以 a 和 0 的公约数就是 a 的所有约数，其中最大的就是 |a|。这个性质在编程中处理边界情况（比如我们的 n=1）时特别有用。

好啦，这道题的讲解就到这里啦。是不是感觉豁然开朗了呢？只要掌握了 GCD 的这个小性质，问题就迎刃而解了。希望这篇题解能帮到你喵~ 如果还有问题，随时可以再来找我哦！

题目大意 ​

解题思路 ​

题解代码 ​

知识点介绍 ​

题目大意

解题思路

题解代码

知识点介绍