Codeforces Round 691 - C - Row GCD

题目

https://codeforces.com/contest/1459/problem/C

思路

差分gcd，利用结论（这个结论非常重要）
$\gcd(a_1,a_2,a_3,\cdots,a_{n-1},a_n)=\gcd(a_1,a_2-a_1,a_3-a_2,\cdots,a_{n-1}-a_{n-2},a_n-a_{n-1})$计算
根据差分的性质，对整个序列加上$k$时，只需对$a_1\leftarrow a_1+k$和$a_{n+1}\leftarrow a_{n+1}-k$即可

AC代码

#include <bits/stdc++.h>
#define endl '\n'
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define lowbit(x) (x&-x)
using namespace std;
struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } }_io;
typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 5;
ll a[maxn], b[maxn];

int main()
{
    ll n, m;
    cin >> n >> m;
    for (ll i = 1; i <= n; ++i) cin >> a[i];
    for (ll i = n; i > 0; --i) a[i] -= a[i - 1], a[i] = abs(a[i]);
    for (ll i = 1; i <= m; ++i) cin >> b[i];

    ll ans = 0;
    for (ll i = 2; i <= n; ++i) ans = __gcd(ans, a[i]);
    for (ll i = 1; i <= m; ++i) cout << __gcd(ans, a[1] + b[i]) << " ";
    cout << endl;

    return 0;
}