首页 > 代码库 > 裴蜀定理 BZOJ2299[HAOI2011] 向量
裴蜀定理 BZOJ2299[HAOI2011] 向量
2299: [HAOI2011]向量
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1362 Solved: 632
[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*109<=a,b,x,y<=2*109)
Output
t行每行为Y或者为N,分别表示可以拼出来,不能拼出来
Sample Input
3
2 1 3 3
1 1 0 1
1 0 -2 3
2 1 3 3
1 1 0 1
1 0 -2 3
Sample Output
Y
N
Y
N
Y
HINT
样例解释:
第一组:(2,1)+(1,2)=(3,3)
第三组:(-1,0)+(-1,0)+(0,1)+(0,1)+(0,1)=(-2,3)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int t; 7 long long a,b,x,y,g; 8 long long gcd(long long aa,long long bb){ 9 return (!bb)?aa:gcd(bb,aa%bb); 10 } 11 bool check(long long aa,long long bb){ 12 if(aa%g||bb%g) return 0; 13 return 1; 14 } 15 int main(){ 16 scanf("%d",&t); 17 while(t--){ 18 scanf("%lld%lld%lld%lld",&a,&b,&x,&y); 19 g=gcd(2*a,2*b); 20 if(check(x,y)||check(x+a,y+b)||check(x+b,y+a)||check(x+a+b,y+a+b)) printf("Y\n"); 21 else printf("N\n"); 22 } 23 return 0; 24 }
裴蜀定理 BZOJ2299[HAOI2011] 向量
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。