给两数a,b,大的数b = b - a*k,a*k为不大于b的数,重复过程,直到一个数为0时,此时当前操作人胜。
可以发现如果每次b=b%a,那么GCD的步数决定了先手后手谁胜,而每次GCD的一步过程视为一个子游戏,但是可以发现如果当前可以约的次数大于2,那么此时操作的人可以控制局面,那么考虑所有可约次数大于2的即可。
/** @Date : 2017-10-12 21:46:31
* @FileName: HDU 1525 类bash 博弈.cpp
* @Platform: Windows
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version : $Id$
*/
#include <bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std; const int INF = 0x3f3f3f3f;
const int N = 1e5+20;
const double eps = 1e-8; int main()
{
int a, b;
while(cin >> a >> b && (a || b))
{
int flag = 0;
if(a < b)
swap(a, b);
while(a % b != 0 && b != 0)
{
if(a / b > 1)//可约次数大于2 此时操作的人可以控制局面
break;
flag ^= 1;
a -= b;
swap(a, b);
}
printf("%s wins\n", flag?"Ollie":"Stan");
}
return 0;
}