【BZOJ-2299】向量 裴蜀定理 + 最大公約數

2299: [HAOI2011]向量

Time Limit: 10 Sec??Memory Limit: 256 MB
Submit: 1118??Solved: 488
[Submit][Status][Discuss]

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

3
2 1 3 3
1 1 0 1
1 0 -2 3

Sample Output

Y
N
Y

HINT

樣例解釋：
第一組：(2,1)+(1,2)=(3,3)
第三組：(-1,0)+(-1,0)+(0,1)+(0,1)+(0,1)=(-2,3)

Source

Solution

首先我們把這些東西組合一下，發現其實這些東西其實相當于是4種變換

(x+-2a,y)/(x,y+-2a)

(x+-2b,y)/(x+-2b,y)

(x+a,y+b)

(x+b,y+a)

那么用裴蜀定理判定一下

證明看這里：折越

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int t;
long long d;
long long Gcd(long long a,long long b) {if (b==0) return a; return Gcd(b,a%b);}
bool check(long long a,long long b) {if (!(a%d) && !(b%d)) return 1; return 0;}
long long a,b,x,y;
int main()
{scanf("%d",&t);while (t--){scanf("%lld%lld%lld%lld",&a,&b,&x,&y);d=Gcd(a,b)<<1;if (check(x+a,y+b) || check(x+b,y+a) || check(x+a+b,y+a+b) || check(x,y)) puts("Y");else puts("N");}return 0;
} 

?