【[HAOI2011]向量】

靠瞎猜的数学题

首先我们先对这些向量进行一顿组合，会发现\((a,b)(a,-b)\)可以组合成\((2a,0)\)，\((b,-a)(b,a)\)可以组合成\((2b,0)\)，同理\((0,2a)\)和\((0,2b)\)自然也是可以组合成的

这个\(0\)很有用，可以只对一项考虑

所以如果这个时候有\(2ax+2by=X\),\(2ax+2by=Y\)，就可以满足了

根据贝祖定理如果\((2a,2b)|X\)且\((2a,2b)|Y\)那么这个时候就满足了

之后还有一些情况

加上一个\((a,b)\)，变成\(2ax+2by=X+a\)和\(2ax+2by=Y+b\)
加上一个\((b,a)\)，变成\(2ax+2by=X+b\)和\(2ax+2by=Y+a\)
\((a,b)\)和\((b,a)\)都加上，变成\(2ax+2by=X+a+b\)和\(2ax+2by=Y+a+b\)

还是分别套用贝祖定理就可以解决了

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#define max(a,b) ((a)>(b)?(a):(b))

#define LL long long

#define re register

LL gcd(LL a,LL b)

{

	if(!b) return a;

	return gcd(b,a%b);

}

inline LL read()

{

	char c=getchar();

	LL x=0,r=1;

	while(c<'0'||c>'9')

	{

		if(c=='-') r=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9')

		x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

int T;

LL a,b,x,y,now;

int main()

{

	T=read();

	while(T--)

	{

		a=read(),b=read(),x=read(),y=read();

		if(!a&&!b)

		{

			if(!x&&!y) puts("Y");

				else puts("N");

			continue;

		}

		if(!a||!b)

		{

			if(x%max(a,b)==0&&y%max(a,b)==0) puts("Y");

				else puts("N");

			continue;

		}

		now=gcd(2*a,2*b);

		if(x%now==0&&y%now==0) puts("Y");

			else if((x+a)%now==0&&(y+b)%now==0) puts("Y");

				else if((x+b)%now==0&&(y+a)%now==0) puts("Y");

					else if((x+a+b)%now==0&&(y+a+b)%now==0) puts("Y");

						else puts("N");

	}

	return 0;

}

巴特西

【[HAOI2011]向量】

最新文章

热门文章