大家好，又见面了，我是你们的朋友全栈君。
Description
$AekdyCoin$正在玩一个游戏，该游戏要用到两副牌和一个数轴和一个棋子。
刚开始的时候棋子位于数轴的$0$位置。然后$AekdyCoin$交替的从两副牌中抽取一张牌，然后执行相应的动作。
设这两幅牌为$A,B$。每张牌上面有一个整数$x$，表示$AekdyCoin$可以前进的格数。从$A$中抽牌，则必须向左走$x$个单位；从$B$中抽牌则必须向右走$x$个单位。
现在要求第一次必须从$A$中抽牌，且必须轮流从两幅牌中抽，即抽完$A$后必须抽$B$,抽完$B$后必须抽$A$。
$AekdyCoin$在玩这个游戏的时候想到了一个问题，如果数轴是无限的，那么棋子有无可能到达任意的整数点呢？
Input
第一行有一个整数$T(1\;\leq\;T\;\leq\;5)$代表有$T$组数据。
每组数据的格式如下：
开头给出$A$牌中的牌数量$N$。然后接下去有$N$个数，代表$A$牌中各个牌上面标的整数。
而后给出$B$牌中的牌数量$M$。然后接下去有$M$个数，代表$B$牌中各个牌上面标的整数。
Output
对于每组测试点输出$YES$或者$NO$来代表题目给出的问题。
Sample Input
2
1 1
1 3
2 1 3
1 2
Sample Output
NO
YES
HINT
$1\;\leq\;N,M\;\leq\;10^5$;牌上面的整数在$[1,10^9]$之间。
Solution
跳的顺序为$ABABAB……$
- 跳偶数步
构造序列$c=\{x|x=-a_i+b_j\}$,
则一个$AB$可以看成从$c$中选择一个元素来跳.
$c$能到达的任何一个数记为:$k=x_1c_1+x_2c_2+…+x_nc_n$,则$k$所能表示的最小正整数为$gcd(c)$,即所有非负$gcd(c)$的倍数都能到达.
然后$c$中必须有正数和负数才能到达数轴上所有$gcd(c)$的倍数的点.
- 跳奇数步
因为跳偶数步只能遍历数轴上所有$gcd(c)$的倍数的点,所以$a_i\;mod\;gcd(c)$要满足取遍[1,gcd(c)),这样才能将数轴剩下的点都跳到.
$gcd(c)=gcd(a_i-b_k,a_j-b_k…)$.
$a_i-b_k-(a_j-b_k)=a_i-a_j$,整除$gcd(c)$.
这说明$a$关于模$gcd(c)$同余.
- 结论
若$c$里面都是非正或者非负,则$NO$;
若$gcd(c)=1$,则$YES$;
若$gcd(c)=2$,且$a_i\;mod\;2=1$,则$YES$,否则$NO$;
若$gcd(c)>2$,则根据$a$关于$gcd(c)$同余可知，$a_i\;mod\;gcd(c)$不可能取遍[1,gcd(c)),所以$NO$.
- 计算$gcd(c)$
$c_{i,j}=-a_i+b_j=(b_j-b_1)+(b_1-a_1)+(a_1-a_i)$.
只需计算$gcd(b_j-b_1,b_1-a_1,a_1-a_i)$.
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100005
using namespace std;
typedef long long ll;
int a[N],b[N],n,m,k,t;
bool flag;
inline int gcd(int x,int y){
if(x<0) x=-x;
if(y<0) y=-y;
int r=x%y;
while(r){
x=y;y=r;r=x%y;
}
return y;
}
inline void Aireen(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
a[1]=0;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i)
scanf("%d",&b[i]);
sort(a+1,a+1+n);
sort(b+1,b+1+m);
if((ll)(b[1]-a[n])*(ll)(b[m]-a[1])>=0ll){
puts("NO");continue;
}
if(b[1]!=a[1]) k=gcd(b[1]-a[n],b[1]-a[1]);
else k=b[1]-a[n];
for(int i=1;i<=n;++i)
if(a[i]!=a[1]) k=gcd(k,a[i]-a[1]);
for(int i=1;i<=m;++i)
if(b[i]!=b[1]) k=gcd(k,b[i]-b[1]);
if(k==1||(k==2&&(a[1]&1))){
puts("YES");continue;
}
puts("NO");
}
}
int main(){
freopen("draughts.in","r",stdin);
freopen("draughts.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/155010.html原文链接：https://javaforall.net
