其实可操作相当于只有((a,b),(a,-b),(b,a),(b,-a)),因为加上((-a,-b))相当于减去((a,b)),其他的同理。
那么问题就变成了找到整数(c,d,e,f),使
(c(a,b)+d(a,-b)+e(b,a)+f(b,-a)=(x,y))成立。
化简原方程,得
((c+d)a+(e+f)b=x)
((e-f)a+(c-d)b=y)
根据裴蜀定理,方程(ax+by=c)整数解,当且仅当
(gcd(x,y)|c)成立。
我们设(P(x,y,c))为真表示上式成立,为假表示不成立。
那么这题就是(P(a,b,x) and P(a,b,y))为真,原方就程就有解吗?
并不是。因为这样只能保证(c+d,e+f,c-d,e-f)是整数,而(c=frac{(c+d)+(c-d)}{2},d=frac{(c+d)-(c-d)}{2},e=frac{(e+f)+(e-f)}{2},f=frac{(e+f)-(e-f)}{2})就不一定是整数了。
所以我们不仅要求(P(a,b,x) and P(a,b,y))为真,还要求(c+d,c-d)奇偶性相同,(e+f,e-f)奇偶性相同。
我们(hs(x,y,c,f))表示方程组
(ax+by=c)
(dx+ey=f)
是否存在(a,e)奇偶性相同,(b,d)奇偶性相同的解,为真表示存在,为假表示不存在。
那么我们分类讨论。
1.当(aequiv eequiv bequiv dequiv0(mod 2))时,我们发现(frac{a}{2},frac{b}{2},frac{d}{2},frac{e}{2})的取值范围为整数。
那么我们得到
(frac{a}{2}x+frac{b}{2}y=frac{c}{2})
(frac{d}{2}x+frac{e}{2}y=frac{f}{2})
有解。
根据裴蜀定理,(P(x,y,frac{c}{2}) and P(x,y,frac{f}{2}))为真。
即(P(2x,2y,c) and P(2x,2y,f))为真。
换句话说,当(a,b,d,e)为偶数,(P(2x,2y,c) and P(2x,2y,f))为真则存在解。
2.当(a,e)和(b,d)中有某一组或者两组都是奇数,以(a,e)是奇数为例:
由
(ax+by=c)
(dx+ey=f)
得
((a+1)x+by=c+x)
(dx+(e+1)y=f+y)
这样一来就回到了偶数的情况,即(P(2x,2y,c+x) and P(2x,2y,f+y))为真。
综上所述,当
(P(2x,2y,c) and P(2x,2y,f))
(P(2x,2y,c+x) and P(2x,2y,f+y))
(P(2x,2y,c+y) and P(2x,2y,f+x))
(P(2x,2y,c+x+y) and P(2x,2y,f+x+y))
中有任意一个为真时,(hs(x,y,c,f))为真。
code:
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long x,long long y){
return y?gcd(y,x%y):x;
}
bool P(long long x,long long y,long long c){
return !(c%gcd(x,y));
}
int T;
long long a,b,x,y;
int main(){
scanf("%d",&T);
while(T--)scanf("%lld%lld%lld%lld",&a,&b,&x,&y),printf("%c
",((P(2*a,2*b,x)&&P(2*a,2*b,y))||(P(2*a,2*b,x+a)&&P(2*a,2*b,y+b))||(P(2*a,2*b,x+b)&&P(2*a,2*b,y+a))||(P(2*a,2*b,x+a+b)&&P(2*a,2*b,y+a+b)))?'Y':'N');
return 0;
}