Codeforces Round #691 (Div. 2) C. Row GCD

发表于 更新于 分类于

链接

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

题意

已知长度为 $n$ $(1\le n \le 2 \cdot 10^{5})$ 的序列 $a$ $(1 \le a_i \le 10^{18})$ 和长度为 $m$ $(1\le m \le 2 \cdot 10^{5})$ 的序列 $b$ $(1 \le b_j \le 10^{18})$，对 $j=1,\dots,m$，求 $a_1+b_j,\dots,a_n+b_j$ 的最大公因数。

思路

根据辗转相减法：$\gcd(a,b)=\gcd(a,b-a)$，

推得：$\gcd(a_1,a_2,\dots,a_n)=\gcd(a_1,a_2-a_1,\dots,a_n-a_{n-1})$。

序列每个数都加上一个数，相邻两数差不变。

所以只要求出 $\gcd(a_2-a_1,\dots,a_n-a_{n-1})$，再每次和 $a_1+b_j$ 求最大公因数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
const int N=2e5+5;
int n,m;
LL a[N],b[N];
int main() {
    //freopen("E:/OneDrive/IO/in.txt","r",stdin);
    scanf("%d%d",&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 d=0;
    for(int i=2;i<=n;i++)  d=__gcd(d,a[i]-a[i-1]);
    d=abs(d);
    for(int i=1;i<=m;i++) printf("%lld ",__gcd(d,a[1]+b[i]));
    puts("");
    return 0;
}