取石子游戏题解

题目链接

http://ybt.ssoier.cn:8088/problem_show.php?pid=1218

题目描述

题意分析：
首先只能进行辗转相除，所以很明显先表示出来。当a/b>=2的时候，先手可以操控后面的所有次序，并且一直让自己拿到a/b>=2的情况。
打个比方38/14
辗转的过程如下：
1、38/14=2…10
2、 14/10=1…4
3、 10/4=2…2
4、 4/2=2…0
如果有人先拿到a/b>=2的情况，那么他一定会拿到所有a/b>=2的情况，如果后面没有a/b>=2的情况，他就能改变次序让自己胜利（有点抽象，不懂得在下面留言）。

代码

#include<bits/stdc++.h>
using namespace  std;
typedef long long ll;
bool  js(ll a, ll b)
{
	if (a / b >= 2 || a == b) return true;
	else return !js(b, a - b);//改变次序
}
int main()
{
	while (cin >> n >> m && !(n == 0 && m == 0))//n行
	{
		if (n < m)swap(n, m);
		if (js(n, m))
			cout << "win";
		else
			cout << "lose";
		cout << endl;
	}
}