- 描述
-
Dr. Kong 设计的机器人卡尔非常活泼，既能原地蹦，又能跳远。由于受软硬件设计所限，机器人卡尔只能定点跳远。若机器人站在（X，Y）位置，它可以原地蹦，但只可以在（X，Y），（X，-Y），（-X，Y），（-X，-Y），（Y，X），（Y，-X），（-Y，X），（-Y，-X）八个点跳来跳去。
现在，Dr. Kong想在机器人卡尔身上设计一个计数器，记录它蹦蹦跳跳的数字变化（S，T），即，路过的位置坐标值之和。
你能帮助Dr. Kong判断机器人能否蹦蹦跳跳，拼出数字（S，T）吗？
假设机器人卡尔初始站在（0，0）位置上。
- 输入
- 第一行： K 表示有多少组测试数据。
接下来有K行，每行：X Y S T1≤K≤10000 -2*109 <= X , Y, S, T <= 2*109
数据之间有一个空格。 - 输出
- 对于每组测试数据，输出一行：Y或者为N，分别表示可以拼出来，不能拼出来
- 样例输入
-
3
2 1 3 3
1 1 0 1
1 0 -2 3 - 样例输出
-
Y
N
Y - 来源
- 第七届河南省程序设计大赛
- 八种变换方式，有四对是呈相反状态的，例如(X,Y)和(-X,-Y)。所以只要对剩下的四个状态走若干次(可以是负数次表示走对立状态)
- 能达到(S,T)就好了。不妨令剩下的四种状态为(X,Y) (X,-Y) (Y,X) (Y,-X) ,对应的次数为a1,a2,a3,a4,我们有: S=(a1+a2)*X+(a3+a4)*Y
- T=(a1-a2)*Y+(a3-a4)*X, 容易看出这两个线性方程可以用exgcd求解，如果S,T 不是gcd(X,Y)的整数倍显然不会成立。算出通解之后
- 注意到(a1+a2)+(a1-a2)=2*a1 (a3+a4)+(a3-a4)=2*a3 , 枚举一下系数的奇偶情况看是否对应的两项相加都可以是偶数即可。
- (不保证算法正确性，，但是AC了。
-
#include<iostream>
#include<cstdio>
using namespace std;
#define LL long long
#define mp make_pair
#define pb push_back
#define inf 0x3f3f3f3f
void exgcd(LL a,LL b,LL &d,LL &x,LL &y){
if(!b){d=a;x=;y=;}
else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int main(){
int t;
cin>>t;
while(t--){
LL X,Y,S,T,d;
LL A,B,C,D,x,y;
scanf("%lld%lld%lld%lld",&X,&Y,&S,&T);
exgcd(X,Y,d,A,B);
if(!(S%d==&&T%d==)){
puts("N");
}
else{
bool ok=;
LL d1=Y/d,d2=X/d;
for(int i=-;i<=;++i){
for(int j=-;j<=;++j){
LL _A=A*S/d+i*d1,_B=B*S/d-i*d2;
LL _C=A*T/d+j*d1,_D=B*T/d-j*d2; if((_A+_D)%==&&(_B+_C)%==)
ok=; }
}
ok?puts("Y"):puts("N");
}
}
return ;
}
/*
3
2 1 3 3
1 1 0 1
1 0 -2 3
*/