10402: C.機(jī)器人 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）八個(gè)點(diǎn)跳來跳去。現(xiàn)在，Dr. Kong想在機(jī)器人卡爾身上設(shè)計(jì)一個(gè)計(jì)數(shù)器，記錄它蹦蹦跳跳的數(shù)字變化（S，T），即，路過的位置坐標(biāo)值之和。你能幫助Dr. Kong判斷機(jī)器人能否蹦蹦跳跳，拼出數(shù)字（S，T）嗎？ 假設(shè)機(jī)器人卡爾初始站在（0，0）位置上。Input 第一行： K 表示有多少組測試數(shù)據(jù)。接下來有K行，每行：X Y S T 1≤K≤10000 -2*109 <= X , Y, S, T <= 2*109 數(shù)據(jù)之間有一個(gè)空格。Output 對于每組測試數(shù)據(jù)，輸出一行：Y或者為N，分別表示可以拼出來，不能拼出來Sample Input 3 2 1 3 3 1 1 0 1 1 0 -2 3 Sample Output Y N Y

歐幾里德與擴(kuò)展歐幾里德算法?：http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

/*
思路：（X，Y），（X，-Y），（-X，Y），（-X，-Y），（Y，X），（Y，-X），（-Y，X），（-Y，-X）
雖然八個(gè)點(diǎn)，其實(shí)有用的只有四個(gè)點(diǎn)，其他的四個(gè)點(diǎn)都可以被替代，比如
（x,y）可以替代 （-x, -y） <-> -[(x, y)]
設(shè)這四個(gè)點(diǎn)是(x,y), (x, -y), (y, x), (y,-x)分別經(jīng)過a1, a2, a3, a4次
則有
(a1+a2)x + (a3+a4)y = s; ---> Ax + By = s; （很明顯的不定方程的形式）
(a1-a2)y + (a3-a4)x = t; ---> Dx + Cy = t;
仔細(xì)觀察上述式子， A+D 和 B+C 都是 偶數(shù)
對于Ax + By = s，可以利用exgcd()求出A, B的值，同理也可以求出D,C的值
如果A，B 為等式的解，那么其余的結(jié)為：
A = A + y/gcd(A, B)*t(其中t為任意整數(shù))
B = B + x/gcd(A, B)*t

利用上面的式子， 枚舉 A,B,C,D ,知道 滿足 A+D 和 B+C的結(jié)果為偶數(shù)！
*/　　

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<vector> 6 #include<map> 7 #include<queue> 8 #define MAX 0x3f3f3f3f 9 #define N 550 10 using namespace std; 11 12 long long exgcd(long long a,long long b,long long &x,long long &y) 13 { 14 if(b==0) 15 { 16 x=1; 17 y=0; 18 return a; 19 } 20 long long r=exgcd(b,a%b,x,y); 21 long long t=x; 22 x=y; 23 y=t-a/b*y; 24 return r; 25 } 26 27 /* 28 x = x + b/gcd(a, b)*t; 29 y = y - a/gcd(a, b)*t; 30 */ 31 32 int main() { 33 int k; 34 long long x, y, s, t; 35 scanf("%d", &k); 36 while(k--){ 37 scanf("%lld%lld%lld%lld", &x, &y, &s, &t); 38 long long a, b, c, d, g; 39 g = exgcd(x, y, a, b); 40 c = a; 41 d = b; 42 if(s%g==0 && t%g==0){ 43 a = a*(s/g); 44 b = b*(s/g); 45 c = c*(t/g); 46 d = d*(t/g); 47 bool flag = false; 48 for(int i=-2; i<=2 && !flag; ++i){ 49 long long aa, bb; 50 aa = a+x/g*i; 51 bb = b-y/g*i; 52 for(int j=-2; j<=2 && !flag; ++j){ 53 long long cc, dd; 54 cc = c+x/g*j; 55 dd = d-y/g*j; 56 if((aa+dd)%2==0 && (bb+cc)%2==0) 57 flag = true; 58 } 59 } 60 if(flag) printf("Y\n"); 61 else printf("N\n"); 62 } else { 63 printf("N\n") ; 64 } 65 } 66 return 0; 67 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/hujunzheng/p/4483343.html

總結(jié)

以上是生活随笔為你收集整理的(扩展欧几里德算法)zzuoj 10402: C.机器人的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。