CF1458A-Row GCD
题目:
题目描述:
You are given two positive integer sequences $ a_1, \ldots, a_n $ and $ b_1, \ldots, b_m $ . For each $ j = 1, \ldots, m $ find the greatest common divisor of $ a_1 + b_j, \ldots, a_n + b_j $ .
输入格式:
The first line contains two integers $ n $ and $ m $ ( $ 1 \leq n, m \leq 2 \cdot 10^5 $ ).
The second line contains $ n $ integers $ a_1, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^{18}) $ .
The third line contains $ m $ integers $ b_1, \ldots, b_m $ ( $ 1 \leq b_j \leq 10^{18}) $ .
输出格式:
Print $ m $ integers. The $ j $ -th of them should be equal to GCD $ (a_1 + b_j, \ldots, a_n + b_j) $ .
样例:
样例输入1:
1
2
3
| 4 4
1 25 121 169
1 2 7 23
|
样例输出1:
思路:
实现:
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
31
32
33
34
35
36
37
| // Problem: CF1458A Row GCD
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1458A
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
long long n, m;
const int maxn = 2e5 + 10;
long long a[maxn];
long long gcd(long long a, long long b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int main()
{
yin >> n >> m;
for (int i = 1; i <= n; i++)
yin >> a[i];
long long gc = 0;
for (int i = 2; i <= n; i++)
{
gc = gcd(gc, abs(a[i] - a[i - 1]));
}
for (int i = 1; i <= m; i++)
{
long long x;
yin >> x;
yout << gcd(gc, x + a[1]) << " ";
}
return 0;
}
|