B简单GCD

由辗转相除法知gcd(a,b)=gcd(b,a%b)
即gcd(a,b)=gcd(b,a-kb)(k为非负整数）
所以gcd(a-b,b)=gcd(b,a%b)=gcd(a,b)$\mathrm{（}a\ge b\mathrm{）}（a\; \backslash geq\; b）$
同理$gcd(a1+b,a2+b)=gcd(a2-a1,a1+b)\mathrm{（}a2\ge a1\mathrm{）}gcd(a1+b,a2+b)=gcd(a2-a1,a1+b)（a2\; \backslash geq\; a1）$
所以gcd(a1+b,a2+b,a3+b)
=gcd(a1+b,gcd(a2+b,a3+b))
=gcd(a1+b,gcd(a2+b,a3-a2))
=gcd(a1+b,a2+b,a3-a2)
=gcd(gcd(a1+b,a2+b),a3-a2) =gcd(gcd(a1+b,a2-a1),a3-a2)
=gcd(a1+b,a2-a1,a3-a2)（｛an｝单调不减）
以此类推
gcd(a1+b,a2+b,a3+b,...,an+b)
=gcd(a1+b,a2-a1,a3-a2,...,an-a(n-1))（｛an｝单调不减）

做题当时其实没想这么细，大致想到答案和数列｛an｝的差有关时就把样例中{an}之间的差、差的gcd、b、答案列出来找规律，然后就做出来了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int a[N],gcda,b;
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=n;i>1;i--)a[i]=a[i]-a[i-1];
    gcda=a[2];
    for(int i=3;i<=n;i++)gcda=__gcd(gcda,a[i]);
    for(int i=1;i<=m;i++){
        if(n==1){
            cout<<a[1]+b<<" ";
            continue;
        }
        cin>>b;
        cout<<__gcd(gcda,b+a[1])<<" ";
    }
}