POJ - 2348 Euclid‘s Game（博弈）

POJ - 2348 Euclid’s Game

题目大意
Stan wins和Stan wins进行比赛，给定两个数，每次将两个数中较大的那个减去较小的那个数的整数倍，减去后依然为正整数
直到两个数有一个数为0，先到0的胜利。
Stan wins先手

思路
第一次遇见可以选择的人将获胜
即为当a≥2?b的时候，可以选择转移到(a%b,b)或者( a % b + b , b )``(a%b+b,b)从而产生不同的局势，而这个人足够聪明所以他可以判断出必胜态
所以我们需要找到面临情况这个的人

当a>=2b时，先手者一定可以得到a%b的值，将这个值与b做比较，如果b%(a%b)=0，说明下一个操作的人一定是必胜的，那么自己处于必败态，此时需要做的就是进行a%b+b的操作，将两个数变为a%b+b和b，那么下一个人的操作只能是将两个数变为a%b和b，先手者再次处于必胜态。总的来说就是当a%b=0或者a>=2b的时候先手必胜，其他情况下进行模拟即可，直到出现必胜态，用flag进行计数，当操作的次数为偶数时stan胜利，为奇数时Ollie胜利

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    long long a,b;while(scanf("%lld%lld",&a,&b)!=EOF){
    if(a==0&&b==0) break;if(a<b) swap(a,b);if(a>=2*b){
    puts("Stan wins");continue;}	int flag=0;while(1){
    if(a>=b*2||a%b==0) break;flag++;a-=b;if(a<b) swap(a,b);}if(flag%2) puts("Ollie wins");else puts("Stan wins");}return 0;
}