题意:
两个数列\(A, B\),对每一个\(j\),求\(gcd(a_1+b_j,a_2+b_j,\dots,a_n+b_j)\)
题解:
更相减损术。
更相减损术是两个数之间的情况,但是\(n\)个数之间仍旧适用:任意两个数作差,gcd不变。
至于证明很简单,每个数写成\(k*gcd\)即可。
于是相邻两数差分即可去掉除了第一个数以外的所有\(b_j\)。
然后对于每一个数求一下即可。
注意排序后再差分,不然会出现负数。
#include <bits/stdc++.h>
#define int long long
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read(){
char c; int num, f = 1;
while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
return f * num;
}
const int N = 3e5 + 1009;
int n, m, a[N], g;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
signed main()
{
n = read(); m = read();
for(int i = 1; i <= n; i++) a[i] = read();
if(n == 1) {
for(int i = 1; i <= m; i++)
printf("%lld ", a[1] + read());
return 0;
}
sort(a + 1, a + 1 + n);
for(int i = n - 1; i; i--) a[i + 1] -= a[i];
g = a[2];
for(int i = 3; i <= n; i++) g = gcd(g, a[i]);
for(int i = 1; i <= m; i++) {
printf("%lld ", gcd(g, a[1] + read()));
}
return 0;
}