- 描述
-
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 T
1≤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了。
-
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 #define LL long long 5 #define mp make_pair 6 #define pb push_back 7 #define inf 0x3f3f3f3f 8 void exgcd(LL a,LL b,LL &d,LL &x,LL &y){ 9 if(!b){d=a;x=1;y=0;} 10 else{exgcd(b,a%b,d,y,x);y-=x*(a/b);} 11 } 12 int main(){ 13 int t; 14 cin>>t; 15 while(t--){ 16 LL X,Y,S,T,d; 17 LL A,B,C,D,x,y; 18 scanf("%lld%lld%lld%lld",&X,&Y,&S,&T); 19 exgcd(X,Y,d,A,B); 20 if(!(S%d==0&&T%d==0)){ 21 puts("N"); 22 } 23 else{ 24 bool ok=0; 25 LL d1=Y/d,d2=X/d; 26 for(int i=-2;i<=2;++i){ 27 for(int j=-2;j<=2;++j){ 28 LL _A=A*S/d+i*d1,_B=B*S/d-i*d2; 29 LL _C=A*T/d+j*d1,_D=B*T/d-j*d2; 30 31 if((_A+_D)%2==0&&(_B+_C)%2==0) 32 ok=1; 33 34 } 35 } 36 ok?puts("Y"):puts("N"); 37 } 38 } 39 return 0; 40 } 41 /* 42 3 43 2 1 3 3 44 1 1 0 1 45 1 0 -2 3 46 */