POJ2348 Euclid's Game

2015.01.14 14:07 Wed| 1 visits oi_2015| 2015_刷题日常| Text

Solution

思想那叫一个精巧啊……

转化为多阶段博弈,若在一个时刻某人可以选择由自己还是对方进入下一阶段的博弈,则胜。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m;

int gcd(int a, int b, int d)
{
    if (b == 0) return d ^ 1;
    if (a / b >= 2) return d;
    return gcd(b, a % b, d ^ 1);
}

int main()
{
    while (cin >> n >> m, n || m)
        puts(gcd(max(n, m), min(n, m), 1) ? "Stan wins" : "Ollie wins");
    return 0;
}