[HAOI2011]向量

题目描述

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

说明：这里的拼就是使得你选出的向量之和为(x,y)

输入输出格式

输入格式：

第一行数组组数t，(t<=50000)

接下来t行每行四个整数a,b,x,y (-2*10^9<=a,b,x,y<=2*10^9)

输出格式：

t行每行为Y或者为N，分别表示可以拼出来，不能拼出来

输入输出样例

输入样例#1：
复制

输出样例#1： 复制

Y

N

Y

说明

样例解释：

第一组：(2,1)+(1,2)=(3,3)

第三组：(-1,0)+(-1,0)+(0,1)+(0,1)+(0,1)=(-2,3)

题解来自520dalao%%%

$k(a,b)+q(b,a)+w(a,-b)+c(b,-a)=(x,y)$

--> $(k+w)a+(q+c)b=x, (k-w)b+(q-c)a=y$ .

　　由裴蜀定理可得：$ax+by=c$ ,x和y有整数解的充要条件是 $gcd(a,b)|c$ ，

证明：令$a=pgcd(a,b),\ b=qgcd(a,b)$ ,则原式=$(px+qy)gcd(a,b)=c$ ，显然因为$gcd(a,b)$ 为整数，而要使x和y为整数，则$gcd(a,b)|c$ 。

　　我们回到开始的方程组$(k+w)a+(q+c)b=x,(k-w)b+(q-c)a=y$ 。由裴蜀定理易得:

使$(k+w),(q+c),(k-w),(q-c)$ 均为整数的充要条件是：

$gcd(a,b)|x$ 且$gcd(a,b)|y$ 。但是注意到(k+w),(k-w)有整数解不一定k和w有整数解（(q+c)和(q-c)是同理的）。此时不妨设$(k+w)=f,(k-w)=g$ ,则$k=(f+g)/2,w=(f-g)/2$ ，因为$2|(f+g)$ 且$2|(f-g)$ ，显然要使k和w均为整数则f和g均为偶数或均为奇数（(q+c)和(q-c)同理）。

　　于是我们考虑这四种情况：

　　1、当(k+w)、(k-w)、(q+c)、(q-c)均为偶数时，$(k+w)a+(q+c)b=x$ 提公因数2结合$gcd(a,b)|x $ => $ 2gcd(a,b)|x$ 同理 $gcd(a,b)|y$

　　2、当(k+w)和(k-w)为偶数，(q+c)和(q-c)为奇数时，$(k+w)a+(q+c)b=x$ 先左右两边同加b，再提公因数2 结合$gcd(a,b)|x$ --> $2gcd(a,b)|x+b$ 同理 $2gcd(a,b)|y+a$

　　3、当(k+w)和(k-w)为奇数，(q+c)和(q-c)为偶数时，$(k+w)a+(q+c)b=x$ 先左右两边同加a，再提公因数2 结合$gcd(a,b)|x $ -->$2gcd(a,b)|x+a$ 同理 $2gcd(a,b)|y+b$

　　4、当(k+w)、(k-w)、(q+c)、(q-c)均为奇数时，$(k+w)a+(q+c)b=x$ 先左右两边同加a+b，再提公因数2 结合$gcd(a,b)|x$ --> $2gcd(a,b)|x+a+b$ 同理 $2gcd(a,b)|y+a+b$

　　只要满足上述的任意一种情况，则说明本题k、w、q、c有整数解，说明可行，否则说明无解。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long lol;

 lol a,b,x,y;

 lol gcd(lol a,lol b)

 {

   if (!b) return a;

   return gcd(b,a%b);

 }

 int main()

 {int T,flag;

   cin>>T;

   while (T--)

     {

       scanf("%lld%lld%lld%lld",&a,&b,&x,&y);

       lol d=gcd(*a,*b);

       flag=;

       if (x%d==&&y%d==) flag=;

       if ((x+a)%d==&&(y+b)%d==) flag=;

       if ((x+b)%d==&&(y+a)%d==) flag=;

       if ((x+a+b)%d==&&(y+a+b)%d==) flag=;

       if (flag) printf("Y\n");

       else printf("N\n");

     }

 }

Description

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

说明：这里的拼就是使得你选出的向量之和为(x,y)

Input

第一行数组组数t，(t<=50000)

接下来t行每行四个整数a,b,x,y (-2*10⁹<=a,b,x,y<=2*10⁹)

Output

t行每行为Y或者为N，分别表示可以拼出来，不能拼出来

Sample Input

2 1 3 3

1 1 0 1

1 0 -2 3

Sample Output

HINT