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

蒟蒻whker · 2025-06-30 19:37:11 · 题解

题意

给定 n 个正整数 a_1,a_2,\dots,a_n 以及 q 组询问。对于第 i(1 \le i \le q) 组询问，求出 \gcd(a_1+i,a_2+i,\dots,a_n+i)。然而暴力会 TLE。

方法

注意到最大公因数有以下性质：

这是因为：

这个性质可以推广到多个数的情况。

所以计算所有 a_j - a_1（j \geq 2）的最大公因数，记为 d。 这样就将问题简化为计算 \gcd(a_1 + i, d)。对于每个查询 i，计算该柿子即可。

最后直接输出结果。

代码

#include<bits/stdc++.h>
using namespace std;
int n, q,a[100005],d;
int main() {
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    sort(a+1,a+n+1);
    for (int i=2;i<=n;i++)
        d=__gcd(d,a[i]-a[i - 1]);//根据 gcd 的性质计算 d
    for (int i=1;i<=q;i++)
        printf("%d\n",__gcd(d,a[1]+i));//输出时直接套公式
    return 0;
}