这是一个利用最大公因数（GCD）性质来优化的数论题目。

题目分析

我们需要求出一组数 $a_1+i, a_2+i, \dots, a_n+i$ 的最大公因数。 根据最大公因数的性质（辗转相除法的原理）：$\gcd(x, y) = \gcd(x, y-x)$。 推广到多个数的情况，我们可以得出： $\gcd(c_1, c_2, \dots, c_k) = \gcd(c_1, c_2-c_1, c_3-c_1, \dots, c_k-c_1)$。

将这个性质应用到本题中： $\gcd(a_1+i, a_2+i, \dots, a_n+i) = \gcd(a_1+i, (a_2+i)-(a_1+i), (a_3+i)-(a_1+i), \dots, (a_n+i)-(a_1+i))$ 化简后得到： $= \gcd(a_1+i, a_2-a_1, a_3-a_1, \dots, a_n-a_1)$

我们发现，除了第一项 $a_1+i$ 会随着 $i$ 的变化而变化外，后面的所有项 $a_k - a_1$ 都是固定的常数（即原数组元素之间的差值）。 令 $K = \gcd(|a_2-a_1|, |a_3-a_1|, \dots, |a_n-a_1|)$。这里取绝对值是因为 $\gcd(x, y) = \gcd(x, |y|)$。 实际上，为了计算方便，我们也可以使用相邻两项的差值来计算 $K$，即 $K = \gcd(|a_2-a_1|, |a_3-a_2|, \dots, |a_n-a_{n-1}|)$，这两种方式计算出的 $K$ 是等价的。

算法步骤：

1. 读取 $n$ 和 $q$ 以及数组 $a$。
2. 预处理计算 $K$：计算数组 $a$ 中所有相邻元素差值的绝对值的最大公因数。
   • 初始化 $K = 0$。
   • 遍历数组，更新 $K = \gcd(K, |a_i - a_{i-1}|)$。
3. 对于每一个询问 $i$ ($1 \le i \le q$)：
   • 答案即为 $\gcd(a_1+i, K)$。

特殊情况：

• 如果 $n=1$，没有差值，答案直接为 $a_1+i$。我们的逻辑中如果初始化 $K=0$，且 $\gcd(x, 0) = x$，则该逻辑也通用。

复杂度分析：

• 预处理 $K$ 需要遍历数组，时间复杂度为 $O(n \cdot \log(\max A))$。
• 每次询问只需要进行一次 GCD 计算，时间复杂度为 $O(\log(\max A))$。
• 总时间复杂度约为 $O(n + q)$，在 $n, q \le 10^5$ 的数据范围内可以轻松通过。

C++ 代码实现

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>

// 手写 gcd 函数，确保兼容性
int get_gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

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

    int n, q;
    if (!(std::cin >> n >> q)) return 0;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 计算差值的最大公因数 K
    // 初始 K 为 0，因为 gcd(x, 0) = x
    int K = 0;
    
    // 我们计算相邻两项差值的绝对值的 GCD
    // 数学上等价于所有项与第一项差值的 GCD
    for (int i = 1; i < n; ++i) {
        int diff = std::abs(a[i] - a[i-1]);
        K = get_gcd(K, diff);
    }

    // 处理每一个询问
    for (int i = 1; i <= q; ++i) {
        // 根据推导，答案是 gcd(a[0] + i, K)
        // 注意题目中询问 i 是从 1 到 q，加到数组元素上
        int val = a[0] + i;
        std::cout << get_gcd(val, K) << "\n";
    }

    return 0;
}

这是一个用于生成题目 P13014 [GESP202506 五级] 最大公因数 测试数据的完整 C++ 代码。

该代码会生成 1.in 到 10.in 以及对应的标准答案 1.out 到 10.out。测试点设计覆盖了题目要求的 60% 小数据、100% 大数据，以及各种边界情况（如 $N=1$、常数数列、等差数列等）。

数据生成器代码 (generator.cpp)

您可以将以下代码保存为 generator.cpp，编译并运行。它将在当前目录下生成所有测试文件。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <numeric>
#include <cmath>
#include <random>
#include <algorithm>

using namespace std;

// ==========================================
// 1. 核心解题逻辑 (用于生成 .out 文件)
// ==========================================

// 求最大公因数
int get_gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

// 解决单个测试点并写入文件
void solve_and_write(int n, int q, const vector<int>& a, string filename) {
    ofstream fout(filename);
    
    // 计算数组所有相邻差值绝对值的最大公因数 K
    // 初始 K=0，因为 gcd(x, 0) = x
    int K = 0;
    
    // 如果 N=1，没有差值，K保持为0，答案直接是 a[0] + i
    if (n > 1) {
        for (int i = 1; i < n; ++i) {
            int diff = abs(a[i] - a[i - 1]);
            K = get_gcd(K, diff);
        }
    }
    
    // 处理 q 次询问
    // 询问 i 从 1 到 q，计算 gcd(a[0] + i, K)
    for (int i = 1; i <= q; ++i) {
        int val = a[0] + i;
        fout << get_gcd(val, K) << "\n";
    }
    
    fout.close();
}

// ==========================================
// 2. 数据生成逻辑
// ==========================================

mt19937 rng(time(0));

// 生成 [l, r] 范围内的随机整数
int rand_int(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

void generate_case(int id) {
    int n, q;
    vector<int> a;
    string desc; // 测试点描述

    // 根据测试点编号配置参数
    switch(id) {
        case 1: 
            // 60% 数据范围：小规模随机
            n = 10; q = 10; 
            desc = "Small N, Small Q (Random)";
            break;
        case 2:
            // 边界情况：N=1
            n = 1; q = 100; 
            desc = "N=1 Boundary";
            break;
        case 3:
            // 特殊性质：常数数列 (K=0)
            n = 50; q = 50; 
            desc = "Constant Array (All same values)";
            break;
        case 4:
            // 特殊性质：等差数列 (K = 公差)
            n = 50; q = 50; 
            desc = "Arithmetic Progression";
            break;
        case 5:
            // 60% 数据范围：N 较大，Q 较小
            n = 1000; q = 10; 
            desc = "Medium N, Small Q";
            break;
        case 6:
            // 100% 数据范围：N 最大，Q 最小
            n = 100000; q = 1; 
            desc = "Max N, Min Q";
            break;
        case 7:
            // 100% 数据范围：N 最小(>1)，Q 最大
            n = 2; q = 100000; 
            desc = "Min N, Max Q";
            break;
        case 8:
            // 100% 数据范围：完全随机
            n = 100000; q = 100000; 
            desc = "Max N, Max Q (Random)";
            break;
        case 9:
            // 100% 数据范围：K 较大 (所有数都是某数的倍数)
            n = 100000; q = 100000; 
            desc = "Max N, Max Q (Large GCD/K)";
            break;
        case 10:
            // 100% 数据范围：K = 1 (互质情况)
            n = 100000; q = 100000; 
            desc = "Max N, Max Q (Coprime/K=1)";
            break;
    }

    // 生成数组 a 的内容
    a.resize(n);
    if (id == 3) {
        // 常数数列
        int val = rand_int(1, 1000);
        fill(a.begin(), a.end(), val);
    } else if (id == 4) {
        // 等差数列
        int start = rand_int(1, 100);
        int diff = rand_int(1, 10);
        for(int i = 0; i < n; ++i) {
            // 保证不超过 1000
            a[i] = start + i * diff;
            if (a[i] > 1000) a[i] = 1000; // 截断以符合题意
        }
    } else if (id == 9) {
        // 倍数构造，保证 K 至少为 base
        int base = 50; 
        for(int i = 0; i < n; ++i) {
            a[i] = rand_int(1, 20) * base; 
        }
    } else if (id == 10) {
        // 构造 K=1，放入两个互质的数或者相邻数
        for(int i = 0; i < n; ++i) a[i] = rand_int(1, 1000);
        a[0] = 7; a[1] = 8; // 强制放入相邻数，确保差值为1，K=1
    } else {
        // 默认随机
        for(int i = 0; i < n; ++i) {
            a[i] = rand_int(1, 1000);
        }
    }

    // --- 写入输入文件 (.in) ---
    string in_name = to_string(id) + ".in";
    ofstream fin(in_name);
    fin << n << " " << q << "\n";
    for(int i = 0; i < n; ++i) {
        fin << a[i] << (i == n - 1 ? "" : " ");
    }
    fin << "\n";
    fin.close();

    // --- 计算并写入输出文件 (.out) ---
    string out_name = to_string(id) + ".out";
    solve_and_write(n, q, a, out_name);

    cout << "Generated Case " << id << ": " << desc << endl;
}

int main() {
    // 生成 1 到 10 号测试点
    for(int i = 1; i <= 10; ++i) {
        generate_case(i);
    }
    cout << "All test cases generated successfully!" << endl;
    return 0;
}

测试点覆盖说明

1. Case 1: 小规模随机数据，$N=10, Q=10$，符合 60% 数据点要求，用于基本逻辑验证。
2. Case 2: 边界情况 $N=1$，验证程序在没有差值时的处理逻辑。
3. Case 3: 常数数列，所有 $a_i$ 相同，此时 $K=0$，答案应为 $a_1+i$。
4. Case 4: 等差数列，验证 $K$ 为公差时的逻辑。
5. Case 5: $N$ 较大但 $Q$ 较小，符合 60% 数据点要求的上限。
6. Case 6: $N=10^5, Q=1$，测试预处理 $O(N)$ 的性能。
7. Case 7: $N=2, Q=10^5$，测试查询 $O(Q \log V)$ 的性能。
8. Case 8: 满数据随机，$N, Q = 10^5$，综合压力测试。
9. Case 9: 构造 $a_i$ 为某数倍数，使 $K$ 较大，测试非互质情况。
10. Case 10: 构造包含相邻整数，使 $K=1$，此时所有答案均为 1 (如果 $a_1+i$ 与 1 互质)，测试互质情况。

使用方法

1. 将代码保存为 generator.cpp。
2. 使用 C++ 编译器编译：g++ generator.cpp -o generator。
3. 运行生成的可执行文件：./generator (Windows 下为 generator.exe)。
4. 当前目录下将生成 20 个文件：1.in ~ 10.in 和 1.out ~ 10.out。