题解 P2520 【[HAOI2011]向量】

· · 题解

本质上这个东西只有这样几种操作：

1.x\pm2a$或$y\pm2a 2.x\pm2b$或$y\pm2b 3.x+a,y+b

令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)便可以被构造

#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;
}