题目大意:
题目给出了两个正数a.b
每次操作,大的数减掉小的数的整数倍。一个数变为0 的时候结束。
谁先先把其中一个数减为0的获胜。问谁可以赢。Stan是先手。
题目思路:
无论a,b的值为多少,局面:[a%b,b] 一定会出现。
双方都足够聪明,无论谁都知道这种局面是必胜局面还是必败局面
若是必败局面操作者为了获胜,直接到达[a%b,b]局面就可以(将必败局留给对方)
若是必胜局操作者为了获胜,到达[a%b+b,b]局面(经过对手操作后,将必胜局面留给自己)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MAXSIZE 100005 using namespace std; int Game(int a,int b)
{
int op=;
while()
{
if(a < b) swap(a,b);
if(a%b== || a/b>=) break;
while(a>b && a<*b)
{
a-=b;
op=-op;
//swap(a,b);
}
}
return op;
} int main()
{
int a,b;
while(scanf("%d%d",&a,&b),a+b)
{
int op=Game(a,b);
if(op==)
printf("Stan wins\n");
else
printf("Ollie wins\n");
}
return ;
}