POJ2348_Euclid's Game_必勝态推理

題意

給定兩個整數 a 和 b。Stan 和 Ollie 輪流從較大的數字中減去較小數字的正整數倍，并且相見後的結果不能小于0。Stan先，在自己的回合中将其中一個數變為0的一方獲勝。當雙方都采取最優政策時，誰會獲勝？

思路

假設 b > a （否則可一交換一下）。

如果 b 已經是 a 的倍數，則必勝。

下面讨論 b 不是 a 的倍數的情況：

按照“自由度”的觀點可以分為兩種情況：

1) b - a < a

2)b - a > a

第一種情況，隻能從b中減去a，沒有選擇的餘地。b - a 後得到的是什麼狀态，它就是相反的狀态，是确定的。

第二種情況，存在最大的 x 使 b - a * x < a。那麼我們考慮 b - a * (x - 1)。這之後，就變成了第一種情況，沒有選擇的餘地，結果也已經确定。如果之後的狀态是必敗态，那麼選 (x-1) 就可以了。否則，就選 x。因為 b - a * (x-1) 之後是必勝态的話，b - a * x 則為必敗态。

綜上所述，先遇到自由狀态的一方必勝。

參考資料

http://www.cnblogs.com/Knuth/archive/2009/09/05/1561005.html

連結

http://poj.org/problem?id=2348

代碼

#include<cstdio>
#include<algorithm>

using namespace std;

int a, b;

int main(){
    while(scanf("%d %d", &a, &b) && a && b){
        bool win = true;
        while(){
            if(a > b) swap(a, b);

            if(b % a == ) break;
            if(b - a > a) break;
            b -= a;

            win = !win;
        }
        if(win) puts("Stan wins");
        else puts("Ollie wins");
    }
    return ;
}