「Bzoj 2299」「HAOI2011」 向量 (Gcd+裴蜀定理)

BZOJ 2299
题意：给出向量$(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)$，请你判断是否能拼出向量$(x_0,y_0)$

观察发现只有$(2a,0), (2b,0), (0,2b), (0,2a), (b,a), (-b,-a), (-a,-b), (a,b)$种向量，并且后面的$4$种每种只会最多用一次。那么可以设方程

$$
\begin{cases}
2ax+2by=x_0 \\
2bx+2ax=y_0
\end{cases}
$$

根据裴蜀定理，有解的充要条件是

$$
gcd(2a,2b)|x_0 ,gcd(2a,2b)|y_0
$$

对于后面四种向量，由于每种最多用一次，分类讨论使用后再列方程判即可，因为$gcd$负数的绝对值和正数的相同，所以只需要讨论正数的即可。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL _a, _b, x, y, d;

    LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a % b);}
    LL chk(LL x, LL y) {return x % d == 0 && y % d == 0;}

    void clean() {
    }
    int solve() {
        clean();
        cin >> _a >> _b >> x >> y;
        d = gcd(2ll * _a, 2ll * _b);
        if (chk(x, y) || chk(x + _a, y + _b) || chk(x + _b, y + _a) || chk(x + _a + _b, y + _a + _b)) return puts("Y"), 0; 
        puts("N");
        return 0;
    }
}
int main() {
    int t; scanf("%d", &t);
    while (t--) flyinthesky::solve();
    return 0;
}