G5016 [GESP202506 五级] 最大公因数 题解

知识点：最大公约数、差分性质、多查询。

解题思路

以首项a为基准，求所有其他项与a之差的最大公约数g。第i次统一加i后的答案为gcd(a+i,g)。

为什么正确

共同加数不改变元素之间的差，而一组数的最大公约数等于首项与所有差值的最大公约数。

易错点

各查询中的i是题目规定的增加量；全部原数相等时g=0，仍可用gcd(x,0)。

复杂度

时间O((n+q)log A)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    long long a;
    cin>>a;
    long long g=0;
    for(int i=1;i<n;i++) {
        long long x;
        cin>>x;
        g=gcd(g,abs(x-a));
    }
    for(int i=1;i<=q;i++)cout<<gcd(a+i,g)<<"\n";
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。