[BZOJ2299] [HAOI2011]向量

本文主要是介绍[BZOJ2299] [HAOI2011]向量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=2299

题目大意

给你一对数a,b，你可以任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量，问你能不能拼出另一个向量(x,y)。

题解

其实就是$(a,b),(a,-b),(b,a),(b,-a)$四个，设分别用它们的次数为$t_1,t_2,t_3,t_4$
然后列方程组

$$a(t_1+t_2)+b(t_3+t_4)=x\\a(t_3-t_4)+b(t_1-t_2)=y$$
我们很容易发现两数之和和之差奇偶性是相同的
就用扩展欧几里德解出来然后调整再判奇偶性即可

varv,l:longint;a,b,aa,bb,x,y,xx,yy,o,p,q,r,tt:int64;
function gcd(a,b:int64):int64;
beginif b=0 then gcd:=a else gcd:=gcd(b,a mod b);
end;procedure exgcd(a,b:int64;var x,y:int64);
var c:int64;
beginif b=0then begin x:=1; y:=0; endelse begin exgcd(b,a mod b,x,y); c:=x; x:=y; y:=c-y*(a div b); end;
end;beginreadln(v);for l:=1 to v dobeginreadln(a,b,x,y);tt:=gcd(a,b); if (x mod tt<>0)or(y mod tt<>0) then begin writeln('N'); continue; end;xx:=x div tt; yy:=y div tt; aa:=a div tt; bb:=b div tt;exgcd(aa,bb,o,p); o:=xx*o; p:=xx*p;exgcd(aa,bb,q,r); q:=yy*q; r:=yy*r;aa:=aa mod 2; bb:=bb mod 2;if (o mod 2=r mod 2)and(p mod 2=q mod 2) then begin writeln('Y'); continue; end;if (((o mod 2<>r mod 2)and(p mod 2=q mod 2))or((o mod 2=r mod 2)and(p mod 2<>q mod 2)))and(((aa=0)and(bb=1))or((aa=1)and(bb=0))) then begin writeln('Y'); continue; end;if (o mod 2<>r mod 2)and(p mod 2<>q mod 2)and((aa=1)or(bb=1)) then begin writeln('Y'); continue; end;writeln('N');end;
end.

这篇关于[BZOJ2299] [HAOI2011]向量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---