[exgcd] zzu oj 10402 C.機器人
來源：程序員人生 發布時間：2015-05-27 08:02:55 閱讀次數：2542次
題意：
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
