题解 P2520 【[HAOI2011]向量】

本质上这个东西只有这样几种操作： >$1.x\pm2a$或$y\pm2a$ >$2.x\pm2b$或$y\pm2b$ >$3.x+a,y+b$ >$4.x+b,y+a$(减可以加两次加回来) 令$A=2a,B=2b,d=\gcd(A,B)$ 对于一对$(x,y)$若其能被构造 那么一定存在一组$(i,j),(u,v)$，使得： $$iA+jB=x,uA+vB=y$$ 根据裴蜀定理 >$a,b\in\mathbb Z,(a,b)=d\Rightarrow\forall x,y\in \mathbb Z$,$d|ax+by$ >特别地，$\exists x,y\in\mathbb Z,ax+by=d$ 所以必须要$d|x$且$d|y$ 这样$(x,y)$才能被构造 然后对于一对$(x,y)$又有四种情况 >$1.(x,y)$ >$2.(x+a,y+b)$ >$3.(x+b,y+a)$ >$4.(x+a+b,y+a+b)$ 只要一种情况满足$(x,y)$便可以被构造 ```cpp #include<cstdio> int T,x,y,a,b;long long d; int gcd(int a,int b){return !b?a:gcd(b,a%b);} inline bool ok(long long x,long long y){return x%d==0&&y%d==0;} int main(){ scanf("%d",&T); while(T--){ scanf("%d%d%d%d",&a,&b,&x,&y);d=gcd(a,b)<<1;x%=d;y%=d;a%=d;b%=d; if((ok(x,y)||ok(x+a,y+b)||ok(x+b,y+a)||ok(x+a+b,y+a+b)))puts("Y"); else puts("N"); } return 0; } ```