(擴充歐幾裡德算法)zzuoj 10402: C.機器人

/*

思路：（X，Y），（X，-Y），（-X，Y），（-X，-Y），（Y，X），（Y，-X），（-Y，X），（-Y，-X）

雖然八個點，其實有用的隻有四個點，其他的四個點都可以被替代，比如

（x,y）可以替代 （-x, -y） <-> -[(x, y)]

設這四個點是(x,y), (x, -y), (y, x), (y,-x)分别經過a1, a2, a3, a4次

則有

(a1+a2)x + (a3+a4)y = s; ---> Ax + By = s; （很明顯的不定方程的形式）

(a1-a2)y + (a3-a4)x = t; ---> Dx + Cy = t;

仔細觀察上述式子， A+D 和 B+C 都是 偶數

對于Ax + By = s，可以利用exgcd()求出A, B的值，同理也可以求出D,C的值

如果A，B 為等式的解，那麼其餘的結為：

A = A + y/gcd(A, B)*t(其中t為任意整數)

B = B + x/gcd(A, B)*t

利用上面的式子， 枚舉 A,B,C,D ,知道 滿足 A+D 和 B+C的結果為偶數！

*/