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

· · 题解

题意

给定正整数序列 a_1,a_2,\dots,a_n，对于每个查询 i，求序列 a_1+i,a_2+i,\dots,a_n+i 的最大公因数。

做法

最大公因数的性质有：

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

对于查询 i 有：

\gcd(a_1+i,a_2+i,\dots,a_n+i)=\gcd(a_1+i,(a_2+i)-(a_1+i),\dots,(a_n+i)-(a_1+i))=\gcd(a_1+i,a_2-a_1,\dots,a_n-a_1)

先停一下，有的同学有疑惑：上面的是怎么推导出来的？

对于 \gcd 有一个性质：\ 对于任意整数集合 \{x_1, x_2, \dots, x_k\} 和任意整数 t，有：

\gcd(x_1, x_2, \dots, x_k) = \gcd(x_1, x_2-x_1, x_3-x_1, \dots, x_k-x_1)

证明：\ 设 g = \gcd(x_1,x_2,\dots,x_k)，则：

  2. 因此 g 整除 x_j-x_1（对所有 j）。
  3. 故 g 是 \{x_1,x_2-x_1,\dots,x_k-x_1\} 的公因数。

反之，设 g' = \gcd(x_1,x_2-x_1,\dots,x_k-x_1)，则：

  2. 因此 g' 整除 x_j=(x_j-x_1)+x_1（对所有 j）。
  3. 故 g' 是 \{x_1, x_2, \dots, x_k\} 的公因数。

综上可得 g = g'。

利用性质 \gcd(x,y,z)=\gcd(x,y-x,z-x)。

我们考虑预处理差值的最大公因数

令 d_i=a_{i+1}-a_1 (i=1,2,\dots,n-1)，计算：

D=\gcd(d_1,d_2,\dots,d_{n-1})

每个查询的答案简化为：

\gcd(a_1+i,D)

CODE

#include<iostream>
#include<algorithm>
using namespace std;
int a[100005],d[100005],n,q;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    int D=0;
    for(int i=2;i<=n;i++)d[i-1]=a[i]-a[1];
    D=d[1];
    for(int i=2;i<n;i++)D=gcd(D,d[i]);
    for(int i=1;i<=q;i++){
        cout<<gcd(a[1]+i,D)<<"\n";
    }
}