Codeforces 1459 Row GCD（GCD，结论）

本文主要是介绍Codeforces 1459 Row GCD（GCD，结论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You are given two positive integer sequences 𝑎1,…,𝑎𝑛 and 𝑏1,…,𝑏𝑚. For each 𝑗=1,…,𝑚 find the greatest common divisor of 𝑎1+𝑏𝑗,…,𝑎𝑛+𝑏𝑗.

Input
The first line contains two integers 𝑛 and 𝑚 (1≤𝑛,𝑚≤2⋅105).

The second line contains 𝑛 integers 𝑎1,…,𝑎𝑛 (1≤𝑎𝑖≤1018).

The third line contains 𝑚 integers 𝑏1,…,𝑏𝑚 (1≤𝑏𝑗≤1018).

Output
Print 𝑚 integers. The 𝑗-th of them should be equal to GCD(𝑎1+𝑏𝑗,…,𝑎𝑛+𝑏𝑗).

Example
inputCopy
4 4
1 25 121 169
1 2 7 23
outputCopy
2 3 8 24

题意：
对于$1\le j\le m$，求$gcd(a[1]+b[j],a[2]+b[j],a[3]+b[j]...)$的值

思路：
由辗转相除法：$gcd(a,b)=gcd(a-b,b)$
所以$gcd(a,b,c,d,e,f,...,z)=gcd(a-z,b-z,c-z,d-z,...,z)$，
由此原式中每个数多加的$b[j]$可以忽略，只有最后一个数要考虑加上$b[n]$，预处理出差分值的$gcd$，再与$a[n]+b[j]$作$gcd$运算即可。

ps:注意负数

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
ll a[maxn],b[maxn];ll gcd(ll n,ll m) {return m == 0 ? n : gcd(m,n % m);
}int main() {int n,m;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]);}if(n == 1) {for(int i = 1;i <= m;i++) {printf("%lld ",a[1] + b[i]);}return 0;}ll now = 0;for(int i = 2;i <= n;i++) {if(!now) now = abs(a[i] - a[i - 1]);else now = gcd(now,abs(a[i] - a[i - 1]));}for(int j = 1;j <= m;j++) {ll ans = gcd(now,a[n] + b[j]);printf("%lld ",ans);}return 0;
}

这篇关于Codeforces 1459 Row GCD（GCD，结论）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---