题目描述

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

  数据范围：\(T\leq 50000,-2\times 10^9\leq a,b,x,y\leq 2\times 10^9\)。

分析

  \((a,b)\) 和 \((-a,-b)\) 这种方向相反的向量是等价的，因此有用的向量只有四个：\((a,b),(a,-b),(b,a)(b,-a)\)。

  问题转化成求整数 \(A,B,C,D\)，使得 \(A(a,b)+B(a,-b)+C(b,a)+D(b,-a)=(x,y)\) 有解。

  化简一下：

\[\begin{cases}(A+B)a+(C+D)b=x\\ (C-D)a+(A-B)b=y \end{cases} \]

  根据裴蜀定理，方程 \(ax+by=c\) 有整数解，当且仅当 \(\gcd (a,b)\mid c\) 成立。

  回到原问题，当 \(\gcd(a,b)\mid x\) 且 \(\gcd(a,b)\mid y\) 时，\(A+B,C+D,A-B,C-D\) 一定有整数解。但是这不能保证 \(A,B,C,D\) 有整数解，比如 \(A+B,A-B\) 的奇偶性不同时，\(A,B\) 都是带 \(0.5\) 的小数。所以还需要要求 $A+B,A-B $ 奇偶性相同，\(C+D,C-D\) 奇偶性相同。

  分四种情况讨论：

  \(1.A+B,A-B,C+D,C-D\) 都是偶数：

\[\begin{cases}\frac{(A+B)}{2}·2a+\frac{(C+D)}{2}·2b=x\\ \frac{(C-D)}{2}·2a+\frac{(A-B)}{2}·2b=y \end{cases} \]

  即 \(\gcd(2a,2b)\mid x\) 且 \(\gcd(2a,2b)\mid y\)。

  \(2.A+B,A-B,C+D,C-D\) 都是奇数：

\[\begin{cases}\frac{(A+B)+1}{2}·2a+\frac{(C+D)+1}{2}·2b=x+a+b\\ \frac{(C-D)+1}{2}·2a+\frac{(A-B)+1}{2}·2b=y+a+b \end{cases} \]

  即 \(\gcd(2a,2b)\mid x+a+b\) 且 \(\gcd(2a,2b)\mid y+a+b\)。

  \(3.A+B,A-B\) 是偶数，\(C+D,C-D\) 是奇数：

\[\begin{cases}\frac{(A+B)}{2}·2a+\frac{(C+D)+1}{2}·2b=x+b\\ \frac{(C-D)+1}{2}·2a+\frac{(A-B)}{2}·2b=y+a \end{cases} \]

  即 \(\gcd(2a,2b)\mid x+b\) 且 $\gcd(2a,2b)\mid y+a $。

  \(4.A+B,A-B\) 是奇数，\(C+D,C-D\) 是偶数：

\[\begin{cases}\frac{(A+B)+1}{2}·2a+\frac{(C+D)}{2}·2b=x+a\\ \frac{(C-D)}{2}·2a+\frac{(A-B)+1}{2}·2b=y+b \end{cases} \]

  即 \(\gcd(2a,2b)\mid x+a\) 且 \(\gcd(2a,2b)\mid y+b\)。

  上述四种情况有任意一个为真，则能拼出向量 \((x,y)\)。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        long long a,b,x,y;
        scanf("%lld %lld %lld %lld",&a,&b,&x,&y);
        long long gcd=__gcd(2*a,2*b);
        if((x%gcd==0&&y%gcd==0)||((x+a+b)%gcd==0&&(y+a+b)%gcd==0)||((x+b)%gcd==0&&(y+a)%gcd==0)||((x+a)%gcd==0&&(y+b)%gcd==0))
            puts("Y");
        else
            puts("N");
    }
    return 0;
}