显然要开始写式子
$k_1a+k_2b=x$
$k_3a+k_4b=y$
首先如果上面两个式子只要有一个没有整数解就一定不合法
如果存在 $k_1+k_2=k_3+k_4$ 那就有解咯
考虑一下发现只要 $k_1+k_2$ 和 $k_3+k_4$ 奇偶性相同即可，因为比较少的那个可以补上 $(a,b)+(-a,-b)$
考虑 $k_1+k_2$ 的关系，设 $d=gcd(a,b)$，则有 $(k_1+pb/d)a+(k_2-pa/d)b=x$ 一定成立，并且由裴蜀定理可知仅当 $p$ 为整数时成立
所以如果 $pb/d$ 和 $pa/d$ 的奇偶性不同，那么 $k_1+k_2$ 的既可以是奇数也可以是偶数，那么一定有解
$k3+k4$ 也是同理
如果 $k_1+k_2$ 和 $k_3+k_4$ 的奇偶性不同，并且 $pb/d$ 和 $pa/d$ 奇偶性相同，那么不管怎么变化奇偶性都不同，一定无解
当然多一些关于 $0$ 的特判总是没错的，把负数转成正数也同样不会影响答案
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } ll T,a,b,x,y; ll exgcd(ll a,ll b,ll &x,ll &y) { if(!b) { x=1,y=0; return a; } ll d=exgcd(b,a%b,x,y); ll t=x; x=y; y=t-a/b*y; return d; } int main() { T=read(); while(T--) { a=read(),b=read(),x=read(),y=read(); if(!a&&!b) { if(!x&&!y) printf("Y "); else printf("N "); continue; } if(a<0) a=-a; if(b<0) b=-b; if(a<b) swap(a,b); ll k1,k2,d1=exgcd(a,b,k1,k2); if(x%d1) { printf("N "); continue; } ll k3,k4,d2=exgcd(a,b,k3,k4); if(y%d2) { printf("N "); continue; } k1*=x/d1; k2*=x/d1; k3*=y/d2; k4*=y/d2; if((!a||!b) || ((k1+k2)%2+2)%2==((k3+k4)%2+2)%2 ) { printf("Y "); continue; } if(((a/d1)&1)^((b/d1)&1) || ((a/d2)&1)^((b/d2)&1) ) printf("Y "); else printf("N "); } return 0; }