一道相似的题目：pku acm 2348 Euclid's Game 
Description 
Two players, Stan and Ollie, play, starting with two natural numbers. Stan, the first player, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be nonnegative. Then Ollie, the second player, does the same with the two resulting numbers, then Stan, etc., alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0, and thereby wins. For example, the players may start with (25,7): 


         25 7
         11 7
          4 7
          4 3
          1 3
          1 0

an Stan wins. 

分析：                   （m, n）                 (m = k×n + r, k≥2, 0<r<n)
               /            |                   \
              /1            |2                   \k
    ((k-1)×n + r, n) ((k-2)×n + r, n) ……((k-k)×n + r, n)
       /
      /
((k-2)×n + r, n)……
可见其决策树具有相似性，如：
                         (25, 7)
                  /1        |2         \3
              (18, 7)    (11, 7)     (4, 7)
            /1       \2     |
        (11, 7)    (4, 7) (4, 7)
           |
        (4, 7)
           |
          ……
           |
        (1, 3)
可见，若 m / n ≥ 2,当前出牌者有必赢的策略。
下面证明若对手有多于一种的出牌选择，则不存在必输的情况。（以k = 2为例）
           Stan                  (m, n)            (m = kn + r,0 < r < n)
                              /1        \2
                        (n+r, n)     (r, n)
           Ollie            |
                        (r, n)
若（r，n）能赢，则Stan选择（n+r，n）；反之，选择（r，n）。

而当m/n=1时，胜负取决于对手。故，
stanWins(m, n)
{
    ……
    if k = 1, then
        return ┐ollieWins(m - n, n)
    ……
}


# include <iostream>
using namespace std;

bool ollieWins(int m, int n);
bool stanWins(int m, int n)
{
    int maximum = (m > n ? m : n), minimum = (m < n ? m : n);
    int k = maximum / minimum, r = maximum % minimum;
    if (r == 0) {
        return true;
    } else if (k == 1) {
        return !ollieWins(maximum % minimum, minimum);
    } else {    // m / n > 1
        return true;
    }
}

bool ollieWins(int m, int n)
{
    int maximum = (m > n ? m : n), minimum = (m < n ? m : n);
    int k = maximum / minimum, r = maximum % minimum;
    if (r == 0) {
        return true;
    } else if (k == 1) {
        return !stanWins(maximum % minimum, minimum);
    } else {    // m / n > 1
        return true;
    }
}

int main()
{
    int m, n;
    while (cin >> m >> n) {
        if (m == 0 && n == 0) {
            break;
        }
        if (stanWins(m, n)) {
            cout << "Stan wins" << endl;
        } else {
            cout << "Ollie wins" << endl;
        }
    }
    return 0;
}