第七届河南省赛10402: C.机器人(扩展欧几里德)

10402: C.机器人

Time Limit: 2 Sec Memory Limit: 128 MB Submit: 53 Solved: 19 [Submit][Status][Web Board]

Description

Dr. Kong 设计的机器人卡尔非常活泼，既能原地蹦，又能跳远。由于受软硬件设计所限，机器人卡尔只能定点跳远。若机器人站在（X，Y）位置，它可以原地蹦，但只可以在（X，Y），（X，-Y），（-X，Y），（-X，-Y），（Y，X），（Y，-X），（-Y，X），（-Y，-X）八个点跳来跳去。

现在，Dr. Kong想在机器人卡尔身上设计一个计数器，记录它蹦蹦跳跳的数字变化（S，T），即，路过的位置坐标值之和。

你能帮助Dr. Kong判断机器人能否蹦蹦跳跳，拼出数字（S，T）吗？

假设机器人卡尔初始站在（0，0）位置上。

Input

第一行： K 表示有多少组测试数据。

接下来有K行，每行：X Y S T

1≤K≤10000 -2*10⁹<= X , Y, S, T <= 2*10⁹

数据之间有一个空格。

Output

对于每组测试数据，输出一行：Y或者为N，分别表示可以拼出来，不能拼出来

Sample Input

Sample Output

Y

N

Y

HINT

Source

第七届河南省赛

题解：机器人在一个区域内随便跳，记录坐标变化值；每给两组数据都有

(a1+a2)x + (a3+a4)y = s; ---> Ax + By = s;
(a1-a2)y + (a3-a4)x = t; ---> Cx + Dy = t;

由此可见A+C,和B+D都是偶数；所以给定Ax + By = s;Cx + Dy = t;

若有转换成立必定有A+D,和B+C都是偶数；所以转换为求两个方程式的解，解出x,y;也就是上面的A,B,C,D;然后判断有没有解；

代码：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

#define SI(x) scanf("%d",&x)

#define mem(x,y) memset(x,y,sizeof(x))

#define PI(x) printf("%d",x)

#define P_ printf(" ")

const int INF=0x3f3f3f3f;

typedef long long LL;

LL ex_gcd(LL a,LL b,LL &x,LL &y){

	if(!b){

		x=1;

		y=0;

		return a;

	}

	LL d=ex_gcd(b,a%b,x,y);

	LL temp=x;

	x=y;

	y=temp-a/b*y;

	return d;

}

int main(){

	int K;

	LL X,Y,S,T;

	SI(K);

	while(K--){

		scanf("%lld%lld%lld%lld",&X,&Y,&S,&T);

		LL gcd,a,b,c,d;

		gcd=ex_gcd(X,Y,a,b);

		if(S%gcd!=0||T%gcd!=0){

			puts("N");continue;

		}

		c=a*T/gcd;d=b*T/gcd;

		a*=S/gcd;b*=S/gcd;

		LL x1,y1,x2,y2;

		int flot=0;

		for(int t1=-2;t1<=2;t1++){

			x1=a+Y/gcd*t1;y1=b-X/gcd*t1;

			for(int t2=-2;t2<=2;t2++){

				x2=c+Y/gcd*t2;y2=d-X/gcd*t2;

			if((x1+y2)%2==0&&(x2+y1)%2==0)flot=1;

			}

		}

		if(flot)puts("Y");

		else puts("N");

	}

	return 0;

}

巴特西