ZigZagK的博客
[裴蜀定理]BZOJ2299(HAOI2011)【向量】题解
2018年2月28日 16:25
BZOJ
查看标签

题目概述

问能否用任意个向量 $(\pm a,\pm b)$ 和 $(\pm b,\pm a)$ 组合出向量 $(x,y)$ 。

解题报告

显然只有这么几种方法:

$x\pm 2a,x\pm 2b,y\pm 2a,y\pm 2b$

$x+a且y+b,x+b且y+a$

而且后两种方法至多用一次(用多次等价于上面的方法)。

所以暴枚后面两种方法是否使用,然后就是判断:

$2f_1a+2f_2b=x$

$2g_1a+2g_2b=y$

这就是扩展欧几里得判断是否有解的问题,所以用裴蜀定理就行了。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;

int te;LL a,b,x,y,r;

inline void Abs(LL &x) {if (x<0) x=-x;}
LL gcd(LL a,LL b) {if (!b) return a;return gcd(b,a%b);}
inline bool check(LL x,LL y) {return !(x%r)&&!(y%r);}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%lld%lld%lld%lld",&a,&b,&x,&y);
        if (!a&&!b) {puts((!x&&!y)?"Y":"N");continue;}
        Abs(a);Abs(b);Abs(x);Abs(y);if (a>b) swap(a,b),swap(x,y);r=gcd(a<<1,b<<1);
        puts(check(x,y)||check(x+a,y+b)||check(x+b,y+a)||check(x+a+b,y+a+b)?"Y":"N");
    }
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!