欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

#691 (Div. 2) C. Row GCD(最大公约数的性质)

程序员文章站 2024-03-20 11:54:40
...
题目描述

You are given two positive integer sequences a1,…,an and b1,…,bm. For each j=1,…,m find the greatest common divisor of a1+bj,…,an+bj.

Input

The first line contains two integers n and m (1≤n,m≤2⋅105).
The second line contains n integers a1,…,an (1≤ai≤1018).
The third line contains m integers b1,…,bm (1≤bj≤1018).

Output

Print m integers. The j-th of them should be equal to GCD(a1+bj,…,an+bj).

Example

input
4 4
1 25 121 169
1 2 7 23
output
2 3 8 24

题目大意

给你n个数a[],和m个数b[]。问 g c d ( b [ i ] + a [ 1 ] , b [ i ] + a [ 2 ] , … … , b [ i ] + a [ n ] ) gcd(b[i]+a[1],b[i]+a[2],……,b[i]+a[n]) gcd(b[i]+a[1],b[i]+a[2],,b[i]+a[n]) 的值(1<=i<=m)。

题目分析

我们知道 g c d ( a , b ) = g c d ( a , b − a ) gcd(a,b)=gcd(a,b-a) gcd(a,b)=gcd(a,ba)
因此: g c d ( a + x , b + x , c + x , d + x ) gcd(a+x,b+x,c+x,d+x) gcd(a+x,b+x,c+x,d+x)
= g c d ( a + x , b + x − a − x , c + x − b − x , d + x − c − x ) gcd(a+x,b+x-a-x,c+x-b-x,d+x-c-x) gcd(a+x,b+xax,c+xbx,d+xcx)
= g c d ( a + x , b − a , c − b , d − c ) gcd(a+x,b-a,c-b,d-c) gcd(a+x,ba,cb,dc)

这样答案就出来了。
g c d ( b [ i ] + a [ 1 ] , b [ i ] + a [ 2 ] , … … , b [ i ] + a [ n ] ) gcd(b[i]+a[1],b[i]+a[2],……,b[i]+a[n]) gcd(b[i]+a[1],b[i]+a[2],,b[i]+a[n])
= g c d ( b [ i ] + a [ 1 ] , a [ 2 ] − a [ 1 ] , … … , a [ n ] − a [ n − 1 ] ) gcd(b[i]+a[1],a[2]-a[1],……,a[n]-a[n-1]) gcd(b[i]+a[1],a[2]a[1],,a[n]a[n1])

代码如下
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <queue>
#include <vector>
#include <set>
#include <bitset>
#include <algorithm>
#define LL long long
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=2e5+5,mod=1e9+7;
LL a[N],b[N]; 
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]);
	LL res=0;
	for(int i=2;i<=n;i++) res=__gcd(res,a[i]-a[i-1]);
	
	for(int i=1;i<=m;i++)
	{
		LL ans=__gcd(res,a[1]+b[i]);
		printf("%lld ",abs(ans));
	}
	return 0; 
}
相关标签: Codeforces