一本通-1218：取石子游戏（基础博弈）

【题目描述】 有两堆石子,两个人轮流去取。每次取的时候,只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍，最后谁能够把一堆石子取空谁就算赢。

比如初始的时候两堆石子的数目是25和7。

25 7 → 11 7 → 4 7 → 4 3 → 1 3 → 1 0     选手1取    选手2取    选手1取    选手2取    选手1取

最后选手1（先取的）获胜，在取的过程中选手2都只有唯一的一种取法。

给定初始时石子的数目，如果两个人都采取最优策略，请问先手能否获胜。

【输入】 输入包含多数数据。每组数据一行，包含两个正整数a和b，表示初始时石子的数目。

输入以两个0表示结束。

【输出】 如果先手胜，输出"win"，否则输出"lose"

【输入样例】 34 12 15 24 0 0

【输出样例】 win lose

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

bool judge(int a, int b) 
{
    int sign = 1; //1代表第一个人，0代表第二个
    if (b > a) std::swap(a, b);

    if (!a || !b) return sign;

    while (a / b < 2) {
        sign = (sign + 1) % 2;
        a -= b;

        if (!a || !b) return (sign + 1) % 2;
        if (b > a) std::swap(a, b);
    }

    return sign;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int a, b;
    while ((cin >> a >> b) && a && b) {
        if (judge(a, b)) cout << "Stan wins" << endl;
        else cout << "Ollie wins" << endl;
    }

    return 0;
}

假设石子数目为(a,b)且a >= b,如果[a/b] >= 2则先手必胜,如果[a/b]<2,那么先手只有唯一的一种取法。[a/b]表示a除以b取整后的值。

这道题和HDU 1525是一个题。另外这道题的测试数据没有考虑a -= b后a为0的情况，不然在HDU 1525会RE。

首先考虑特殊情况，其中一堆石子是0，那么胜负态确定，所以如果中间状态到了这一步，那么可以直接输出结果。

题目限定了都是正数，考虑a == b的情况，那么先手必输，因为只有一种取法，就是将其中一堆都取走，那么后面的人就获胜了。

因为a,b(假设a > b)的状态先手的人肯定有办法使这个状态变为a%b, b，那么先手的人是有办法去判断a % b, b的状态是必胜还是必败。假如a >= 2 * b，那么先手的人必胜，因为：

• 如果a%b, b的状态是必胜，那么先手的策略是取出石子，让状态变为b + a%b, b，那么接下来的人只能取走b个，那么先手的人遇到了必胜态。
• 如果a%b, b是必败态，那么先手就取走石子让状态变为a%b, b，那么下一个人就面临必败态，于是先手获胜。

所以[a/b]>=2先手必胜，不然先手只有一种取法，需要迭代去判断。