2023.6.17 每日一题

SanCai-Newbie / 2023-06-17 / 原文

原题链接

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();
    }
}