Row GCD
题意
对于两个正整数序列 a 1 、 a 2 、 a 3 、 … a n a_1、a_2、a_3、 \dots a_n a1、a2、a3、…an 和 b 1 、 b 2 、 b 3 … b m b_1、b_2、b_3 \dots b_m b1、b2、b3…bm 对于每个 j = 1 、 2 、 … j j = 1、2、\dots j j=1、2、…j 找到 a 1 + b j 、 a 2 + b j + a 3 + b j 、 … a n + b j a_1 + b_j、a_2+b_j + a_3+b_j、\dots a_n+b_j a1+bj、a2+bj+a3+bj、…an+bj 的最大公约数
思路
首先我们要知道一个定理 g c d ( a 1 , a 2 , a 3 , … , a n ) = = g c d ( a 1 , a 2 − a 1 , a 3 − a 2 , … , a n − a n − 1 ) gcd(a_1,a_2,a_3, \dots,a_n) == gcd(a_1,a_2-a_1,a_3-a_2,\dots ,a_n-a_{n-1}) gcd(a1,a2,a3,…,an)==gcd(a1,a2−a1,a3−a2,…,an−an−1)
所以可以将题目变形成求 g c d ( a 1 + b j , a 2 − a 1 . a 3 − a 2 , … , a n − a n − 1 ) gcd(a_1+b_j,a_2-a_1.a_3-a_2,\dots,a_n-a_{n-1}) gcd(a1+bj,a2−a1.a3−a2,…,an−an−1)
预处理一下 g c d ( a 2 − a 1 . a 3 − a 2 , … , a n − a n − 1 ) gcd(a_2-a_1.a_3-a_2,\dots,a_n-a_{n-1}) gcd(a2−a1.a3−a2,…,an−an−1) 即可
代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
const int N = 200010;
int n, m;
LL a[N], b[N];
void solve() {
cin >> 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 j = 1; j <= m; ++j) {
cout << abs(gcd(res, a[1] + b[j])) << " ";
}
cout << endl;
}
int main() {
//int t; cin >> t;
//while (t--)
solve();
return 0;
}