取石子游戏
Time Limit: 1000MS Memory limit: 65536K
题目描述
给定a、b两堆石子，甲乙两人做取石子游戏。游戏规则是：每次可以从其中一堆取走任意数目的石子，且每次只能在其中一堆中取；最后没有石子可取的人判为输。现在已知甲先取石子，问他在先取石子的情况下能否获胜（假设甲乙两位选手足够聪明）。
 

输入
第一行是一个正整数t，下面t行每行有两个整数a,b(0<=a,b<=10^9)，分别表示两堆石子的数目
输出
对于每一行输入，若甲能取胜，则输出"Yes"，否则输出"No"。（不包括引号部分）
示例输入
2
107 109
10000007 1
示例输出
Yes
Yes
链接地址：http://acm.sdut.
#include<stdio.h>
void main()
{
    int i,m,n,t;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%d%d",&m,&n);
        if(m==n)
            printf("No\n");
        else
            printf("Yes\n");
    }
}
为什么上面这段程序就能AC呢？小弟愚昧，百思不得其解，求高手指点一二。

这是涉及博弈论及数论的知识。这两门学科在计算机科学中应用非常广泛，大家应该掌握一些其中的基础知识。
这个取石子游戏是尼姆博弈的一个子集（尼姆博弈讨论的是三堆物品的情况），及(0, a, b)的情况。当a = b时是一个奇异局势，面对这一局势者必败。
(0, 0)必败；
(1, 1)必败；
(n, n)先取者无论从哪堆中取走k个(k <= n)，后取者都可从另一堆中也取走k个，使之后的局势仍保持 a = b。先取必败。
而当a != b时（设a < b)，面对这一局势者都可以从多的一堆中取走b - a的物品使之变为奇异局势，必胜。

表示看不懂。。。

懂得真多。佩服佩服。

回复 laoyang103

所谓局势就是当前石子的状态，即每堆有几个。
所谓奇异局势就是当参与者面对它就必输的局势。

(a, b)表示有两堆，第一堆有a个，第二堆有b个。因为堆没有顺序，可以设a <= b。

(0, 0)是每堆都没有石头的状态。没有可拿的，按照游戏规则面对这一状态的人铁定输了。
(0, 1)，一堆已经拿完了，另一堆只有一个石子，这时甲拿走这一石子，乙将面对(0, 0)状态，乙输了。
(0, k)，同上，甲只要拿走这k个石子就胜了。因为他们都足够聪明，不会故意败给对方。
以上讨论完了只有一堆的情况。下面讨论有两堆的情况
(1, 1)，因为一次只能从一堆中拿。这里题目的描述有点问题，所谓的任意数目不包括0（即不拿）。所以不管甲拿走哪个石子，乙都可以拿走另一个取胜。
(a, b)， 0 < a，b这分两种情况，即a == b和 a != b，就是我上一贴讨论的核心内容，通过以上的分析应该可以理解了吧，我就不赘述了。

面对相等的两堆石头，先取的那个人必输。
如果不等，先取的那个从多的那一堆取走比少的那一堆多出的几个石头，变成相等的两堆。然后后取的那个面对相等的两堆，他又是先取，必输。