P13014 [GESP202506 五级] 最大公因数

题目描述

对于两个正整数 $a,b$，他们的最大公因数记为 $\gcd(a,b)$。对于 $k > 3$ 个正整数 $c_1,c_2,\dots,c_k$，他们的最大公因数为：

$$\gcd(c_1,c_2,\dots,c_k)=\gcd(\gcd(c_1,c_2,\dots,c_{k-1}),c_k) $$

给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$ 以及 $q$ 组询问。对于第 $i(1 \le i \le q)$ 组询问，请求出 $a_1+i,a_2+i,\dots,a_n+i$ 的最大公因数，也即 $\gcd(a_1+i,a_2+i,\dots,a_n+i)$。

输入格式

第一行，两个正整数 $n,q$，分别表示给定正整数的数量，以及询问组数。

第二行，$n$ 个正整数 $a_1,a_2,\dots,a_n$。

输出格式

输出共 $q$ 行，第 $i$ 行包含一个正整数，表示 $a_1+i,a_2+i,\dots,a_n+i$ 的最大公因数。

输入输出样例 #1

输入 #1

5 3
6 9 12 18 30

输出 #1

1
1
3

输入输出样例 #2

输入 #2

3 5
31 47 59

输出 #2

4
1
2
1
4

说明/提示

对于 $60\%$ 的测试点，保证 $1 \le n \le 10^3$，$1 \le q \le 10$。

对于所有测试点，保证 $1 \le n \le 10^5$，$1 \le q \le 10^5$，$1 \le a_i \le 1000$。

题目解析 这道题要求我们计算对于每个查询值 i（从1到q），求出所有 a_j + i 的最大公因数。例如，对于数组 [1, 3] 和 i=1，我们需要计算 gcd(1+1, 3+1) = gcd(2,4) = 2。

关键思路 问题转化： 通过数学性质，我们可以将求多个数的最大公因数转化为求这些数与基准数（如第一个数）的差的最大公因数。具体来说： gcd(a1+i, a2+i, ..., an+i) = gcd(a1+i, gcd(a2-a1, a3-a1, ..., an-a1)) 这是因为任意两个数的差在求最大公因数时保持不变。

计算基准公因数： 我们先计算所有其他元素与第一个元素的差的绝对值的最大公因数，记为 g0。例如，对于数组 [1, 3, 5]，g0 = gcd(|3-1|, |5-1|) = gcd(2,4) = 2。

处理查询： 对于每个查询 i，我们只需要计算 gcd(a1 + i, g0)。例如，当 i=1 时，gcd(1+1, 2) = gcd(2,2) = 2。

特殊情况处理：

如果数组只有一个元素，那么结果直接是 a1 + i，因为单个数的最大公因数就是它本身。

如果所有元素都相同，那么 g0 = 0，此时最大公因数就是 a1 + i。

#include <iostream>
#include <vector>
#include <cmath> // 用于abs函数
#include <algorithm> // 用于swap函数
using namespace std;

// 计算两个数的最大公因数（非递归实现）
long long my_gcd(long long a, long long b) {
    // 处理负数：最大公因数只关心绝对值
    a = abs(a);
    b = abs(b);
    // 特殊情况：如果两个数都是0，则返回0（题目保证不会出现）
    if (a == 0 && b == 0) 
        return 0;
    // 确保a >= b，简化计算
    if (a < b) 
        swap(a, b);
    // 欧几里得算法
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    long long n, q;
    cin >> n >> q;
    vector<long long> a(n);
    // 读入数组
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 情况1：只有一个元素
    if (n == 1) {
        for (long long i = 1; i <= q; i++) {
            cout << a[0] + i << '\n'; // 直接输出a1 + i
        }
        return 0;
    }

    // 情况2：多个元素
    // 步骤1：计算所有其他元素与第一个元素的差的最大公因数g0
    long long g0 = 0;
    for (int j = 1; j < n; j++) {
        long long diff = abs(a[j] - a[0]); // 计算差的绝对值
        g0 = my_gcd(g0, diff); // 更新最大公因数
    }

    // 步骤2：处理每个查询
    for (long long i = 1; i <= q; i++) {
        long long x = a[0] + i; // 计算a1 + i
        long long ans = my_gcd(g0, x); // 计算答案
        cout << ans << '\n';
    }

    return 0;
}