Description
给你一对数a,b,你可以任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量,问你能不能拼出另一个向量(x,y)。
说明:这里的拼就是使得你选出的向量之和为(x,y)
Input
第一行数组组数t,(t<=50000)
接下来t行每行四个整数a,b,x,y (-2*109<=a,b,x,y<=2*109)
Output
t行每行为Y或者为N,分别表示可以拼出来,不能拼出来
Sample Input
3
2 1 3 3
1 1 0 1
1 0 -2 3
Sample Output
Y
N
Y
HINT
样例解释:
第一组:(2,1)+(1,2)=(3,3)
第三组:(-1,0)+(-1,0)+(0,1)+(0,1)+(0,1)=(-2,3)
有意义的向量就四个(a,b),(a,-b),(b,a),(b,-a)
设系数为x1,x2,x3,x4
可列不定方程
a(x1+x2)+b(x3+x4)=x
b(x1-x2)+a(x3-x4)=y
设x1+x2=d1,x3+x4=d2,x1-x2=d3,x3-x4=d4
借不定方程
然后判断是否有合法解
合法解就是d1+d2 is even,d3+d4 is even
program bzoj2299; type group= record x,y:longint; end; var ok:boolean; i,j,o,t,a,b,x,y:longint; q,p,u,v,pq,pp,pu,pv:int64; stu:group; procedure swap (var a,b:longint);inline; begin if a=b then exit; a:=a xor b; b:=a xor b; a:=a xor b; end; function gcd (a,b:longint):longint;inline; var i:longint; begin while a mod b <>0 do begin i:=a mod b; a:=b; b:=i; end; exit(b); end; function extgcd(a,b:longint):group; var ans,temp:group; begin if b=0 then begin ans.x:=1; ans.y:=0; exit(ans); end; temp:=extgcd(b,a mod b); ans.x:=temp.y; ans.y:=temp.x-a div b * temp.y; exit(ans); end; begin read(t); while t>0 do begin dec(t); read(a,b,x,y); if (a=0)and(b=0) then begin if (x<>0)or(y<>0) then writeln('N') else writeln('Y'); continue; end; a:=abs(a); b:=abs(b); if a>b then swap(a,b); if a=0 then begin if (x mod b = 0)and(y mod b = 0) then writeln('Y') else writeln('N'); continue; end; o:=gcd(a,b); if (x mod o <> 0)or(y mod o <> 0) then begin writeln('N'); continue; end; stu:=extgcd(a,b); q:=stu.x*int64(x div o); p:=stu.y*int64(x div o); pq:=b div o; pp:=a div o; stu:=extgcd(b,a); u:=stu.x*int64(y div o); v:=stu.y*int64(y div o); pu:=a div o; pv:=b div o; ok:=false; for i:=0 to 1 do for j:=0 to 1 do if ((q+pq*i+u+pu*j) and 1 = 0)and((p-pp*i+v-pv*j) and 1 = 0) then ok:=true; if ok then writeln('Y') else writeln('N'); end; end.