《P2520 [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×109≤a,b,x,y≤2×109)。

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

Y N Y

说明/提示

样例解释

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

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

代码实现：

// luogu-judger-enable-o2 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline ll rd() { ll x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } ll T,A,B,X,Y; ll exgcd(ll a,ll b,ll &x,ll &y) { if(!b) { x=1,y=0; return a; } ll d=exgcd(b,a%b,x,y); ll t=x; x=y; y=t-a/b*y; return d; } int main() { T=rd(); while(T--) { A=rd(),B=rd(),X=rd(),Y=rd(); if(!A&&!B) { if(!X&&!Y) printf("Y\n"); else printf("N\n"); continue; } if(A<0) A=-A; if(B<0) B=-B; if(A<B) swap(A,B); ll k1,k2,d1=exgcd(A,B,k1,k2); if(X%d1) { printf("N\n"); continue; } ll k3,k4,d2=exgcd(A,B,k3,k4); if(Y%d2) { printf("N\n"); continue; } k1*=X/d1; k2*=X/d1; k3*=Y/d2; k4*=Y/d2; if((!A||!B) || ((k1+k2)%2+2)%2==((k3+k4)%2+2)%2 ) { printf("Y\n"); continue; } if(((A/d1)&1)^((B/d1)&1) || ((A/d2)&1)^((B/d2)&1) ) printf("Y\n"); else printf("N\n"); } return 0; }