[exgcd] zzu oj 10402 C.机器人
来源：程序员人生 发布时间：2015-05-27 08:02:55 阅读次数：2369次
题意：
Description
Dr. Kong 设计的机器人卡尔非常活泼，既能原地蹦，又能跳远。由于受软硬件设计所限，机器人卡尔只能定点跳远。若机器人站在（X，Y）位置，它可以原地蹦，但只可以在（X，Y），（X，-Y），（-X，Y），（-X，-Y），（Y，X），（Y，-X），（-Y，X），（-Y，-X）8个点跳来跳去。
现在，Dr. Kong想在机器人卡尔身上设计1个计数器，记录它蹦蹦跳跳的数字变化（S，T），即，途经的位置坐标值之和。
你能帮助Dr. Kong判断机器人能否蹦蹦跳跳，拼出数字（S，T）吗？
假定机器人卡尔初始站在（0，0）位置上。
Input
第1行：
K 表示有多少组测试数据。
接下来有K行，每行：X Y S T
1≤K≤10000 ⑵*109 <= X , Y, S, T <= 2*109
数据之间有1个空格。
Output
对每组测试数据，输出1行：Y或为N，分别表示可以拼出来，不能拼出来
Sample Input
3
2 1 3 3
1 1 0 1
1 0 ⑵ 3
Sample Output
Y
N
Y
思路：
首先我们设(a1,a2...a8)代表每一个位置被踩了多少次。
然后我们发现a1和a4其实可以和成1个。由于a4+1就等a1⑴。
这样就剩下4个变量了（a1,a2,a5,a6)
这时候候我们列完方程：
S=(a1+a2)X+(a5+a6)Y
T=(a5-a6)X+(a1-a2)Y
现在只要求是不是有1个整数4元组（a1,a2,a5,a6）满足这两个方程就OK了。
个人YY了1个方法。。
假定 A=a1+a2 B=a5+a6 C=a5-a6 D=a1-a2
只要（A+D）是偶数并且 （B+C）是偶数就能够了。
由于通过A+D可以求出a1和a2，通过B+C可以求出a5和a6。
然后其实这是1个这样的方程
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）的情况
枚举判断1下就有了答案。
然后注意1下，上述全是给予X,Y都非零的情况。
零的情况需要特判1下。
代码：
#include"stdio.h"
#include"algorithm"
#include"string.h"
#include"iostream"
#include"queue"
#include"map"
#include"string"
#define ll long long
using 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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
