[博弈]HDU-1525

http://acm.hdu.edu.cn/showproblem.php?pid=1525

↑ 题目链接

题目大意：

两个玩家，斯坦和奥利，从两个自然数开始。斯坦，第一个玩家，从两个数中较大的数减去两个数中较小的数的任何正倍数，前提是得到的数必须是非负的。然后第二个玩家奥利，对得到的两个数字做同样的处理，然后是斯坦，交替进行，直到一个玩家能够从较大的数中减去较小的数的倍数，得到0，从而获胜。例如，玩家可以从(25,7)开始:
25 7
11 7
4 7
4 3
1 3
1 0

解题思路：首先这两个人是极度聪明的。
这点非常重要。
非常重要。
a b 两个数字(a>b)
有以下几种情况
1：a%b==0(包含a==b) 那么此时 先手必胜 直接成0了。
2：a>2倍的b 此时 操作后将变为 b a%b(极限操作 就是b<a<2*b) 操作完之后的人清楚这样是胜还是败的
2.1 如果这样是胜的 那么先手操作完就赢了
2.2 如果这样是败的 那么先手操作成a%b+b b后手只能操作成 b a%b 这样回到了2.1的情况 所以还是先手胜
3.b<a<2b 这样的情况就大-小循环 直到满足1/2的条件时 即可判断谁能赢。

#include
#include