CF1459C. Row GCD

链接: https://codeforces.com/contest/1459/problem/C

题目描述

现有两组均由正整数组成的序列 a_1,…,a_n , b_1, … , b_m.

对每个 j=1,…,m , 找到 a_1+b_j, … , a_n+b_j 的最大公因数

Input

4 4
1 25 121 169
1 2 7 23

Output

2 3 8 24

Solution

结论题 直接上结论
\gcd(a_1,a_2,a_3…a_n)=\gcd(a_1,\gcd(a2-a1,a3-a2…a_n-a_{n-1}))
代码

#include
#define ll long long
const int N = 2e5+10;
int n,m;
ll a[N],b[N];
ll gcd(ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b); 
}
int main(){
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    for(int i=1;i<=m;++i)
        scanf("%lld",&b[i]);
    std::sort(a+1,a+1+n);
    ll G = a[2]-a[1];
    if(n==1){
        for(int i=1;i<=m;++i){
            printf("%lld ",a[1]+b[i]);
        }
        return 0;
    }
    for(int i=3;i<=n;++i)
        G=gcd(G,a[i]-a[i-1]);
    for(int i=1;i<=m;++i){
        printf("%lld ",gcd(a[1]+b[i],G));
    }
    return 0;
}