您當(dāng)前位置：首頁(yè) > php開源 > php教程 > [exgcd] zzu oj 10402 C.機(jī)器人

[exgcd] zzu oj 10402 C.機(jī)器人

來(lái)源：程序員人生發(fā)布時(shí)間：2015-05-27 08:02:55 閱讀次數(shù)：2546次

題意：

Description

Dr. Kong 設(shè)計(jì)的機(jī)器人卡爾非常活潑，既能原地蹦，又能跳遠(yuǎn)。由于受軟硬件設(shè)計(jì)所限，機(jī)器人卡爾只能定點(diǎn)跳遠(yuǎn)。若機(jī)器人站在（X，Y）位置，它可以原地蹦，但只可以在（X，Y），（X，-Y），（-X，Y），（-X，-Y），（Y，X），（Y，-X），（-Y，X），（-Y，-X）8個(gè)點(diǎn)跳來(lái)跳去。

現(xiàn)在，Dr. Kong想在機(jī)器人卡爾身上設(shè)計(jì)1個(gè)計(jì)數(shù)器，記錄它蹦蹦跳跳的數(shù)字變化（S，T），即，途經(jīng)的位置坐標(biāo)值之和。

你能幫助Dr. Kong判斷機(jī)器人能否蹦蹦跳跳，拼出數(shù)字（S，T）嗎？

假定機(jī)器人卡爾初始站在（0，0）位置上。

Input

第1行： K 表示有多少組測(cè)試數(shù)據(jù)。

接下來(lái)有K行，每行：X Y S T

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

數(shù)據(jù)之間有1個(gè)空格。

Output

對(duì)每組測(cè)試數(shù)據(jù)，輸出1行：Y或?yàn)?/span>N，分別表示可以拼出來(lái)，不能拼出來(lái)

Sample Input

3 2 1 3 3 1 1 0 1 1 0 ⑵ 3

Sample Output

Y N Y

思路：

首先我們?cè)O(shè)(a1,a2...a8)代表每一個(gè)位置被踩了多少次。

然后我們發(fā)現(xiàn)a1和a4其實(shí)可以和成1個(gè)。由于a4+1就等a1⑴。

這樣就剩下4個(gè)變量了（a1,a2,a5,a6)

這時(shí)候候我們列完方程：

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

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

現(xiàn)在只要求是不是有1個(gè)整數(shù)4元組（a1,a2,a5,a6）滿足這兩個(gè)方程就OK了。

個(gè)人YY了1個(gè)方法。。

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

只要（A+D）是偶數(shù)并且（B+C）是偶數(shù)就能夠了。

由于通過(guò)A+D可以求出a1和a2，通過(guò)B+C可以求出a5和a6。

然后其實(shí)這是1個(gè)這樣的方程

S=AX+BY 和 T=CX+DY

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

固然如果無(wú)解直接就是“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; }

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生