题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2299
题意:给出一对数a,b,任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量,能不能拼出另一个向量(x,y)。
思路:(a,b)和(-a,-b)是两两相反的,那么最后就是4个,(a,b),(-a,b),(b,a),(-b,a)。我们设四个最后使用的个数为t1,t2,t3,t4,那么有:
令k=Gcd(a,b),d=2*k。(A1,B1)和(A2,B2)奇偶共四种情况:偶偶、偶奇、奇偶、奇奇。若为偶偶,那么x和y均是d的倍数;若x和y均是d的倍数,那么必然存在偶数A1,A2使得A1*a+A2*b=x成立,存在偶数B1,B2使得B1*b+B2*a=y成立,进而有解。因此这是充要的。其他三种情况类似。
i64 a,b,x,y;
i64 d;
i64 Gcd(i64 a,i64 b)
{
if(b==0) return a;
return Gcd(b,a%b);
}
int ok(i64 x,i64 y)
{
return x%d==0&&y%d==0;
}
int main()
{
rush()
{
RD(a,b); RD(x,y);
if(a==0&&b==0)
{
if(x==0&&y==0) puts("Y");
else puts("N");
continue;
}
d=Gcd(a,b)<<1;
if(ok(x,y)||ok(x-a,y-b)||ok(x-b,y-a)||ok(x-a-b,y-a-b)) puts("Y");
else puts("N");
}
}