题解 CF1458A 【Row GCD】
Warriors_Cat
2020-12-23 16:44:10
[题面传送门](https://www.luogu.com.cn/problem/CF1458A)。
> 题意：给两个序列 $a_1, ... a_n$ 和 $b_1, ... b_m$。对于每个 $i \in [1, m]$，求出 $\gcd(a_1 + b_i, a_2 + b_i, ..., a_n + b_i)$。
---
### $Solution:$
考虑 $\gcd$ 的一个变式：$\gcd(x, y) = \gcd(x, y - x)(x \le y)$。
于是原式就可以转化为：$\gcd(a_1 + b_i, a_2 - a_1, a_3 - a_2, ..., a_n - a_{n - 1})$。
先预处理 $x = \gcd(a_2 - a_1, a_3 - a_2,... a_n - a_{n - 1})$，对于每个 $i$，直接求出 $\gcd(a_1 + b_i, x)$ 即可。
over，时间复杂度为 $O(n \log a_i)$。
---
### $Code:$
以下为赛时代码。
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
#define int long long
#define fi first
#define se second
#define y1 y_csyakioi_1
#define y0 y_csyakioi_0
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 200010;
int n, m, a[N], b[N], c[N];
inline int gcd(int x, int y){ return y == 0 ? x : gcd(y, x % y); }
inline void work(){
n = read(); m = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= m; ++i) b[i] = read();
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; ++i) c[i] = a[i] - a[i - 1];
int ans = c[2];
for(int i = 2; i <= n; ++i) ans = gcd(ans, c[i]);
for(int i = 1; i <= m; ++i) printf("%lld ", gcd(ans, b[i] + a[1]));
}
signed main(){
int t = 1; while(t--) work();
return 0;
}
```