[C++知识库](HDU - 1525)Euclid‘s Game(博弈)

题目链接：Euclid's Game - HDU 1525 - Virtual Judge (ppsucxtt.cn)

题目大意：有两个玩家,Stan 和 Ollie, 在玩游戏。初始有两个自然数。Stan是先手，每次把大的数字减去小的数字的任意倍数，但是不能使数字变成负数。然后Ollie进行同样的操作，直到有一个玩家使一个数字变为零。

容易知道，对于刚开始给定的m和n（不妨假设m>=n），若m是n的整数倍，显然先手可以通过一步操作直接胜出。

当m>2*n时，先手也必胜，下面给出证明：

不妨设m=k*n+r，m>2*n等价于k>=2，对于先手可以直接进行（m,n）-->( r , n ) 操作，当（ r , n ），为一种必败态时，先手直接获胜，若（ r , n ），为一种必胜态时，先手可以进行

（m,n）-->( r + n , n )操作，这样后手只能进行?( r + n , n )?-->( r ?, n )操作，这样先手就进入了必胜态，也可以取得胜利，所以只要是m>2*n时，先手必胜。

现在我们确定了两种必胜态，一种是m>2*n，另一种是m%n==0，下面我们来讨论m<2*n的情况

若m<2*n,则先手只能进行（m,n）-->( m-n, n )，若n<2*(m-n)则重复进行上述操作，倘若在运行过程中出现两个数的较大数大于较小数的2倍或者可以被较小数整除时，就可以判断胜负了，也就是判断必胜态首先发生在谁身上。

下面上代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
int main()
{
	int m,n;
	while(1)
	{
		
		scanf("%d%d",&m,&n);
		if(m==0&&n==0) break;
		if(m<n) swap(m,n);
		if(m>2*n||m%n==0)
			puts("Stan wins");
		else
		{
			int cnt=1;
			while(m&&n)
			{
				if(m<n) swap(m,n);
				if(m>2*n||m%n==0)
				{
					if(cnt&1) puts("Stan wins");//判断是谁优先进入必胜态 
					else puts("Ollie wins");
					break;
				}
				m-=n;
				cnt++;
			}
		}
	}
	return 0;
}