首页 > 代码库 > 【BZOJ 2299】 2299: [HAOI2011]向量 (乱搞)
【BZOJ 2299】 2299: [HAOI2011]向量 (乱搞)
2299: [HAOI2011]向量
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 1255 Solved: 575Description
给你一对数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 3Sample Output
Y
N
YHINT
样例解释:
第一组:(2,1)+(1,2)=(3,3)
第三组:(-1,0)+(-1,0)+(0,1)+(0,1)+(0,1)=(-2,3)Source
【分析】
目测是随便mod一下判断一下就好了的。
看代码吧。。
就是可以用4个向量表示完全部(2a,0)(2b,0)(a,b)(b,a)
看出来横纵坐标是可以mod gcd(2a,2b)的。
然后直接判断最后是不是(0,0)或者(a,b)或者(b,a)或者(a+b,a+b)什么鬼的?
【对了乘了2记得LL
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define LL long long 8 9 LL myabs(LL x) {return x>0?x:-x;} 10 11 LL gcd(LL a,LL b) 12 { 13 if(b==0) return a; 14 return gcd(b,a%b); 15 } 16 17 int main() 18 { 19 int T; 20 scanf("%d",&T); 21 while(T--) 22 { 23 LL a,b,x,y; 24 scanf("%lld%lld%lld%lld",&a,&b,&x,&y); 25 a=myabs(a);b=myabs(b); 26 if(a==0&&b==0) 27 { 28 if(x==0&&y==0) printf("Y\n"); 29 else printf("N\n"); 30 } 31 else if(a==0||b==0) 32 { 33 if(a==0&&(x%b+b)%b==0&&(y%b+b)%b==0) printf("Y\n"); 34 else if(b==0&&(x%a+a)%a==0&&(y%a+a)%a==0) printf("Y\n"); 35 else printf("N\n"); 36 } 37 else 38 { 39 LL g=gcd(a,b)*2; 40 x=(x%g+g)%g; 41 y=(y%g+g)%g; 42 if(x==0&&y==0) printf("Y\n"); 43 else if(x==a%g&&y==b%g) printf("Y\n"); 44 else if(x==b%g&&y==a%g) printf("Y\n"); 45 else if(x==(a+b)%g&&y==(a+b)%g) printf("Y\n"); 46 else printf("N\n"); 47 48 } 49 } 50 return 0; 51 }
2017-04-05 11:45:22
顺便放一下查到的裴蜀定理
也就是exgcd里面那个东西嘛。。没什么特别的。。
【BZOJ 2299】 2299: [HAOI2011]向量 (乱搞)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。