HDU 1525 Euclid's Game

题目大意:

题目给出了两个正数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 ;
}
上一篇:PAT 乙级真题 1003 我要通过!题解


下一篇:前谷歌首席 Java 架构师谈如何设优秀的 API