[exgcd] zzu oj 10402 C.机器人

题意：

DescriptionInput

第一行：

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

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

数据之间有一个空格。

Output

Sample Input32 1 3 31 1 0 11 0 -2 3Sample OutputYNY

思路：

首先我们设(a1,a2…a8)代表每个位置被踩了多少次。

然后我们发现a1和a4其实可以和成一个。因为a4+1就等a1-1。

这样就剩下4个变量了（a1,a2,a5,a6)

这时候我们列完方程：

S=(a1+a2)X+(a5+a6)Y

T=(a5-a6)X+(a1-a2)Y

现在只要求是否有一个整数四元组（a1,a2,a5,a6）满足这两个方程就OK了。

个人YY了一个方法。。

假设 A=a1+a2 B=a5+a6 C=a5-a6 D=a1-a2

只要（A+D）是偶数并且 （B+C）是偶数就可以了。

因为通过A+D可以求出a1和a2，通过B+C可以求出a5和a6。

然后其实这是一个这样的方程

S=AX+BY 和 T=CX+DY

我们可以用exgcd求出A,B,C,D的通解。

当然如果无解直接就是“N”了。

令tep=gcd(X,Y)

我们可以求出 A=A+k1*(Y/tep) B=B-k1*(X/tep) C=C+k2*(Y/tep) D=D-k2*(X/tep)

然后我很笨的枚举了 A,B,C,D的情况。

因为A,B随k1的奇偶变化 C,D随k2的奇偶变换

总共就两组（A,B）的情况和两组（C,D）的情况

枚举判断一下就有了答案。

然后注意一下，上述全是给予X,Y都非零的情况。

零的情况需要特判一下。

代码：

#include"stdio.h"#include"algorithm"#include"string.h"#include"iostream"#include"queue"#include"map"#include"string"#define ll long longusing namespace std;ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll r=exgcd(b,a%b,x,y),t;t=x;x=y;y=t-a/b*y;return r;}int main(){int t;cin>>t;while(t–){ll a,b,s,tt;scanf("%lld%lld%lld%lld",&a,&b,&s,&tt);if(a==0 && b==0){if(s==0 && tt==0) puts("Y");else puts("N");continue;}else if(a==0 || b==0){if(a==0){if(s%b==0 && tt%b==0) puts("Y");else puts("N");}else{if(s%a==0 && tt%a==0) puts("Y");else puts("N");}continue;}ll x1,y1,x2,y2;ll tep1=exgcd(a,b,x1,y1);ll tep2=exgcd(a,b,x2,y2);if(s%tep1!=0 || tt%tep2!=0){puts("N");continue;}x1=x1*s/tep1;x2=x2*tt/tep2;y1=y1*s/tep1;y2=y2*tt/tep2;int f1,f2,f3,f4,v1,v2,v3,v4;if(x1%2) f1=1;else f1=0;if(y1%2) f2=1;else f2=0;if((b/tep1)%2) f3=f1^1;else f3=f1;if((a/tep1)%2) f4=f2^1;else f4=f2;if(x2%2) v1=1;else v1=0;if(y2%2) v2=1;else v2=0;if((b/tep2)%2) v3=v1^1;else v3=v1;if((a/tep2)%2) v4=v2^1;else v4=v2;if( ((f1+v2)%2==0 && (f2+v1)%2==0) || ((f1+v4)%2==0 && (f2+v3)%2==0) ){puts("Y");continue;}if( ((f3+v2)%2==0 && (f4+v1)%2==0) || ((f3+v4)%2==0 && (f4+v3)%2==0) ){puts("Y");continue;}puts("N");}return 0;}

，人生有一半掌握在上帝那里，另一半攥在自己的手中。