#691 (Div. 2) C. Row GCD（最大公约数的性质）
题目描述
You are given two positive integer sequences a1,…,an and b1,…,bm. For each j=1,…,m find the greatest common divisor of a1+bj,…,an+bj.
Input
The first line contains two integers n and m (1≤n,m≤2⋅105).
The second line contains n integers a1,…,an (1≤ai≤1018).
The third line contains m integers b1,…,bm (1≤bj≤1018).
Output
Print m integers. The j-th of them should be equal to GCD(a1+bj,…,an+bj).
Example
input
4 4
1 25 121 169
1 2 7 23
output
2 3 8 24
题目大意
给你n个数a[]，和m个数b[]。问 g c d ( b [ i ] + a [ 1 ] , b [ i ] + a [ 2 ] , … … , b [ i ] + a [ n ] ) gcd(b[i]+a[1],b[i]+a[2],……,b[i]+a[n]) gcd(b[i]+a[1],b[i]+a[2],……,b[i]+a[n]) 的值（1<=i<=m）。
题目分析
我们知道
g
c
d
(
a
,
b
)
=
g
c
d
(
a
,
b
−
a
)
gcd(a,b)=gcd(a,b-a)
gcd(a,b)=gcd(a,b−a)。
因此：
g
c
d
(
a
+
x
,
b
+
x
,
c
+
x
,
d
+
x
)
gcd(a+x,b+x,c+x,d+x)
gcd(a+x,b+x,c+x,d+x)
=
g
c
d
(
a
+
x
,
b
+
x
−
a
−
x
,
c
+
x
−
b
−
x
,
d
+
x
−
c
−
x
)
gcd(a+x,b+x-a-x,c+x-b-x,d+x-c-x)
gcd(a+x,b+x−a−x,c+x−b−x,d+x−c−x)
=
g
c
d
(
a
+
x
,
b
−
a
,
c
−
b
,
d
−
c
)
gcd(a+x,b-a,c-b,d-c)
gcd(a+x,b−a,c−b,d−c)
这样答案就出来了。
g
c
d
(
b
[
i
]
+
a
[
1
]
,
b
[
i
]
+
a
[
2
]
,
…
…
,
b
[
i
]
+
a
[
n
]
)
gcd(b[i]+a[1],b[i]+a[2],……,b[i]+a[n])
gcd(b[i]+a[1],b[i]+a[2],……,b[i]+a[n])
=
g
c
d
(
b
[
i
]
+
a
[
1
]
,
a
[
2
]
−
a
[
1
]
,
…
…
,
a
[
n
]
−
a
[
n
−
1
]
)
gcd(b[i]+a[1],a[2]-a[1],……,a[n]-a[n-1])
gcd(b[i]+a[1],a[2]−a[1],……,a[n]−a[n−1])
代码如下
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <queue>
#include <vector>
#include <set>
#include <bitset>
#include <algorithm>
#define LL long long
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=2e5+5,mod=1e9+7;
LL a[N],b[N];
int main()
{
int n,m;
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]);
LL res=0;
for(int i=2;i<=n;i++) res=__gcd(res,a[i]-a[i-1]);
for(int i=1;i<=m;i++)
{
LL ans=__gcd(res,a[1]+b[i]);
printf("%lld ",abs(ans));
}
return 0;
}