POJ 2348 Euclid's Game

問題

2つの自然数が与えられ、この自然数についてStanとOllieがゲームを行う。プレーヤは大きい方の数から小さい方の数の倍数を引いて相手プレーヤに渡すことができる。ただし、大きい方から小さい方の倍数を引いて残った数は0以上にならなければいけない。最初にどちらかの数を0にしたプレーヤが勝ちとする。Stanからプレーを始めたとして両者が最適にプレーする時、必勝なのはどちらか。

やりかた

ちょっと前にやって放置していた問題。さっきぼんやり考えていたらできた。

大きい方から引くことのできる小さい方の数の倍数の数は になる。つまり、大きい方から回だけ小さい数を引くことができるということ。その後数の大小は入れ替わる。
大きい方から小さい方の倍数を引く操作はの石がある山から任意の個数の石を取る操作と考えることができるので、このゲームは複数の山から石を取るゲームで、取る山に順序が有るバージョンとも考えられる。
このゲームはあるターンで複数の石を含む山に当たったときに、その山より一つ後の山が後手から始まる場合自分が必敗なら今の山を一つ残して後手に渡すと必勝形に変えられる。そうでなければ今の山は全部取ってしまい、次の山を後手から始めさせればいい。この考えで行くと、結局最初に複数の山に当たるプレーヤが必敗の状態を覆せるので必勝ということになる。

以下ソース。

int main(int argc, char **argv){
  int a, b;
  while(cin >> a >> b, a){
    if(a < b) swap(a, b);
    int turn = 0;
    while(b){
      if(a % b == 0 || a / b >= 2) break;
      a %= b;
      swap(a, b);
      turn++;
    }
    cout << (turn % 2 ? "Ollie wins" : "Stan wins") << endl;
  }
  return 0;
}