CF1459C. Row GCD
链接: https://codeforces.com/contest/1459/problem/C
题目描述
现有两组均由正整数组成的序列 a_1,…,a_n , b_1, … , b_m.
对每个 j=1,…,m , 找到 a_1+b_j, … , a_n+b_j 的最大公因数
Input
4 4
1 25 121 169
1 2 7 23
Output
2 3 8 24
Solution
结论题 直接上结论
\gcd(a_1,a_2,a_3…a_n)=\gcd(a_1,\gcd(a2-a1,a3-a2…a_n-a_{n-1}))
代码
#include
#define ll long long
const int N = 2e5+10;
int n,m;
ll a[N],b[N];
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b);
}
int main(){
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]);
std::sort(a+1,a+1+n);
ll G = a[2]-a[1];
if(n==1){
for(int i=1;i<=m;++i){
printf("%lld ",a[1]+b[i]);
}
return 0;
}
for(int i=3;i<=n;++i)
G=gcd(G,a[i]-a[i-1]);
for(int i=1;i<=m;++i){
printf("%lld ",gcd(a[1]+b[i],G));
}
return 0;
}
0 条评论