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

· · 题解

题目传送门

题目大意

给定 n 个正整数 a_1,\dots,a_n 和 q 组询问。对于第 i(1\le i\le q) 组询问，请求出 \gcd(a_1+i,\dots,a_n+i)。

解法

众不一定周知，最大公约数有一个性质：\gcd(x,y)=\gcd(x,y-x)，利用这个也可以推广到多个数：

\gcd(x,y,z)=\gcd(x,\gcd(y−x,z−x))

利用此性质可以带入原式，有：

\begin{aligned}&\gcd(a_1+i,\cdots ,a_n+i)\\ &=\gcd(a_1+i,(a_2+i)−(a_1+i),(a_3+i)−(a_1+i),…,(a_n+i)−(a_1+i))\\&=\gcd(a_1+i,a_2−a_1,a_3−a_1,…,a_n−a_1)\\&=\gcd(a_1+i,\underline{\gcd(a_2−a_1,a_3−a_1,…,a_n−a_1) })\\ \end{aligned}

注意到画下划线的部分计算不需要用到 i 的参与，可以提前求出，用结果再与 a_1+i 计算最大公因数。

代码

利用函数 __gcd 可以在对数复杂度计算最大公因数。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+1;
int n,q,a[maxn],gcd;
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        gcd=__gcd(gcd,abs(a[i]-a[1]));
    }
    for(int i=1;i<=q;i++){
        cout<<__gcd(gcd,a[1]+i)<<endl;
    }
    return 0;
}

小广告：游记。