原题链接
B: Codeforces Round 691 (Div. 1) - A
B. Row GCD - 1600
题目大意
给定两列大正数 \(a_1,\dots, a_n\) 和 \(b_1,\dots,b_m\)，现在要求 \(a_1 + b_j, \dots, a_n + b_j\) 的最大公约数。
解题思路
暴力一个个找不TLE才怪了，我们需要找到每次运算的公共特征。
我们知道对于gcd有如下性质：
\[\gcd(a,\ b) = \gcd(a,\ b - a) \]这是我们欧几里得算法成立的重要条件。
那么对我们求的式子处理，就得到：
\[\begin{aligned} &\gcd(a_1 + b_j,\ a_2 + b_j,\dots,\ a_n + b_j)\\ =&\gcd(a_1 + b_j,\ a_2 - a_1,\dots,\ a_n - a_1)\\ =&\gcd(a_1 + b_j, gcd\_) \end{aligned} \]这里的 \(gcd\_\) 是恒定值，可以在读入 \(a\) 数列时得到，那么只需要保留一个 \(a_1\) 的值，其他值在读入时优化掉即可。
AC Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
const int MOD = 1e9 + 7;
void solve() {
int n, m;
cin >> n >> m;
n--;
LL a;
cin >> a;
LL gcd_ = 0;
while (n--) {
LL x;
cin >> x;
gcd_ = gcd(gcd_, x - a);
}
gcd_ = abs(gcd_);
while (m--) {
LL x;
cin >> x;
cout << gcd(gcd_, a + x) << ' ';
}
cout << endl;
}
signed main() {
ios;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}