A. Row GCD(更相减损术+gcd的性质)

Problem - 1458A - Codeforces

 

给你两个正整数序列a1,...,an和b1,...,bm。对于每个j=1,...,m，求a1+bj,...,an+bj的最大公除数。

输入
第一行包含两个整数n和m（1≤n，m≤2⋅105）。

第二行包含n个整数a1,...,an（1≤ai≤1018）。

第三行包含m个整数b1,...,bm（1≤bj≤1018）。

输出
打印m个整数。其中第j个应该等于GCD（a1+bj,...,an+bj）。

例子
输入复制
4 4
1 25 121 169
1 2 7 23
输出拷贝
2 3 8 24
题解:
考虑到n,m的范围肯定不能暴力,

既然他让我们求最大公因数,我们想想其性质

1.gcd(a,b) = gcd(a,b-a)

2.gcd(a,b,c) = gcd(a,gcd(b,c)

结合a1+bj,...,an+bj,

我们从这两条性质入手,

我们考虑一下第一条性质

gcd(a1+bj,a2 + bj)  = gcd(a1+bj,a2 - a1)

考虑第二条性质,是不每个i= 2~n都可以转化为 ai - a1

我们只需要先得到gcd(ai-a1,....an-a1) i~n

再对a[1] + b[1~j] 计算即可

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define int long long
int a[200505];
int b[200050];
void solve()
{
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	cin >> a[i];
	for(int i = 1;i <= m;i++)
	cin >> b[i];
	int ma = 0;
	for(int i = 2;i <= n;i++)
	{
		ma = __gcd(ma,abs(a[i]-a[1]));
	}
	for(int i = 1;i <= m;i++)
	{
		int x = a[1] + b[i];
		cout<<__gcd(ma,x)<<" ";
	}
	cout<<"\n";
}
signed main()
{
	int t = 1;
//	cin >> t;
	while(t--)
	{
		solve();
	}
}