「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;
}
------ 本文结束 ------