扩展欧几里德算法)zzuoj 10402: C.机器人

<code>10402: C.机器人</code>

<code>Description</code>

<code>Dr. Kong 设计的机器人卡尔非常活泼，既能原地蹦，又能跳远。由于受软硬件设计所限，机器人卡尔只能定点跳远。若机器人站在（X，Y）位置，它可以原地蹦，但只可以在（X，Y），（X，-Y），（-X，Y），（-X，-Y），（Y，X），（Y，-X），（-Y，X），（-Y，-X）八个点跳来跳去。</code>

<code>现在，Dr. Kong想在机器人卡尔身上设计一个计数器，记录它蹦蹦跳跳的数字变化（S，T），即，路过的位置坐标值之和。</code>

<code>你能帮助Dr. Kong判断机器人能否蹦蹦跳跳，拼出数字（S，T）吗？</code>

<code>假设机器人卡尔初始站在（0，0）位置上。</code>

<code>Input</code>

<code>第一行：             K                表示有多少组测试数据。</code>

<code>接下来有K行，每行：X  Y  S  T    </code>

<code>1≤K≤10000   -2*109 &lt;= X , Y, S, T &lt;= 2*109</code>

<code>数据之间有一个空格。</code>

<code>Output</code>

<code>对于每组测试数据，输出一行：Y或者为N，分别表示可以拼出来，不能拼出来</code>

<code>Sample Input</code>

<code>3</code>

<code>2 1 3 3</code>

<code>1 1 0 1</code>

<code>1 0 -2 3</code>

<code>Sample Output</code>

<code>Y</code>

<code>N</code>

<a></a>

/*

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

虽然八个点，其实有用的只有四个点，其他的四个点都可以被替代，比如

（x,y）可以替代 （-x, -y） &lt;-&gt; -[(x, y)]

设这四个点是(x,y), (x, -y), (y, x), (y,-x)分别经过a1, a2, a3, a4次

则有

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

(a1-a2)y + (a3-a4)x = t; ---&gt; 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的结果为偶数！ 

*/　　

本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/4483343.html，如需转载请自行联系原作者