Essa wanted to meet the most powerful number theorist of all time: Bahosain, but Bahosain does not waste his precious time, so he gave Essa this puzzle in order to test his abilities.
Given two arrays, the second array only has distinct elements, Essa can do the following as many times as he wants to make all numbers in first array equal.
Choose a number from the first array
Add or subtract from it a number in the second array
Replace the number in the first array with the result
Of course, Essa is unworthy of meeting the almighty Bahosain, and he can’t solve this puzzle on his own, so can you help him?
Input
The first line containing two space separated integers n,mn,m (1≤n,k≤1061≤n,k≤106) represent the length of the first and second array.
the second line contains n integers represent the first array (1≤a[i]≤1091≤a[i]≤109)
the third line contains m integers represent the second array (1≤b[i]≤1091≤b[i]≤109)
Output
Print Yes, if it’s possible to make all numbers in first array equal; and No in the opposite case.
Example
Input
5 2
3 6 7 2 5
2 4
Output
No
题意：一次操作就是选择a数组中的一个数，在选择b数组中一个数，a加上或减去b，可以进行任意次操作，使得a数组中数最终都相等，能的话输出Yes，否则输出No。
题解：本来想的是找到a数组中的最大值，然后分别找到max-a[i],找到他们的最大公约数gg，然后在b数组中找看是否存在gg，如果存在输出yes，否则输出No，但是wa了下面是错误的代码：
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=1e6+10;
ll a[N],b[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n,m,i;
cin>>n>>m;
for(i=1;i<=n;i++) cin>>a[i];
for(i=1;i<=m;i++) cin>>b[i];
if(n==1)
{
printf("Yes\n");
return 0;
}
ll maxx=-1;
for(i=1;i<=n;i++)
if(a[i]>maxx) maxx=a[i];
ll gg=0;
for(i=1;i<=n;i++)
if(a[i]!=maxx)
gg=__gcd(gg,maxx-a[i]);
if(gg==0) printf("Yes\n");//所有值都相等
else
{
int flag=0;
for(i=1;i<=m;i++)
{
if(b[i]==gg)
{
flag=1;
break;
}
}
if(flag==0) printf("No\n");
else printf("Yes\n");
}
return 0;
}
后来想了想，发现如果有gg的情况下一定是可以的，但是没有gg的情况下不一定不行，；例如a[]=“3 6 9” b[]=“2 8 11” a中的最大公约数是3，但是b中不含3所以输出No，但是b[2]-b[1]-b[0]=1,如果可以组成1的话必定是可以的，所以正确答案应该输出Yes。造成这种错误的原因就是不含有但是几个数可以通过加减等操作可以组成的也饿同样可以的，但是因为情况太多，无法讨论，所以应该反着思考，看找b的最大公约数是否能行。
gcd(b[0],b[1],b[2],b[3],……，b[n])
如果可以相等的话
max-a[i]=k1 * b[1] + k2 * b[2] + ……+ kn * b[n] ；
= k * (gcd);
所以只有max-a[i]能够整除gcd的话才能写成相等的，否则不能。
这里我选择了用a中的最大值减去各个值，但是选择哪个都是一样的，但是我不太清楚怎么证明，所以没证明……，
下面是AC代码：
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#define ll long long
using namespace std;
const int N=1e6+10;
ll a[N],b[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n,m,i;
cin>>n>>m;
for(i=1;i<=n;i++) cin>>a[i];
for(i=1;i<=m;i++) cin>>b[i];
if(n==1)
{
printf("Yes\n");
return 0;
}
ll maxx=-1;
for(i=1;i<=n;i++)
if(a[i]>maxx) maxx=a[i];
ll gg=0;
for(i=1;i<=n;i++)
gg=__gcd(gg,b[i]);
int flag=0;
for(i=1;i<=n;i++)
if((maxx-a[i])%gg!=0) flag=1;
if(flag==0) printf("Yes\n");
else printf("No\n");
return 0;
}
