大家好，又见面了，我是你们的朋友全栈君。
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)>2a关于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).
代码语言：javascript复制#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.cn/155010.html原文链接：https://javaforall.cn
