Snowdream

問題：
有兩堆石子，數量任意，可以不同。游戲開始由兩個人輪流取石子。游戲規定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數量的石子。最后把石子全部取完者為勝者?，F在給出初始的兩堆石子的數目，如果輪到你先取，假設雙方都采取最好的策略，問最后你是勝者還是敗者。

碰到這道題時我的思路：

設集合A, B分別為先手能贏和后手能贏的二元無序對(x,y)的集合

先從最基礎的開始考慮，(n,0) (n,n) 屬于A，因為這樣的情況先手肯定能贏（n為正整數，下同）

如果存在(a,b)，對于一切n，(a-n,b-n)均屬于A，則(a,b)屬于B
很容易找到一個(2,1)，這是后手肯定能贏的情況

接下來從先手的角度分析，如果他能在移動石子后留給對手(2,1)個石子，那么他就能贏，于是
(2+n,1) (2+n,1+n) (2,1+n) 均屬于 A

找出一個不屬于A的最小對，(5,3)， 這個元素肯定屬于B集合，因為從中任意取出元素后的結果肯定屬于A集合
相應的，(5+n, 3) (5, 3+n), (5+n, 3+n) 均屬于A

這時發現，B集合相對A集合元素少很多，只要找出B集合中元素的特征，就能解決這個問題。

一旦B中包含(x,y)對，A中就會相應的包含(x, y+n), (x+n, y), (x+n,y+n)
由此想出一種構造B集合的方法，設當前構造出的集合為S，a為不在S中的最小的數，即
a = MIN{ x | x 不屬于 (p, q), 對于一切(p, q)屬于S }
則把(a, a+gap)加入B中，其中gap是當前S中所有對之差的最小值+1
 
 構造出的序列為
 (1,2) -> (3, 5) -> (4, 7) -> (6, 10)
 
 到這里這道題目應該已經能過了，不過還有一種達到O(1)的優化，接下來的就不是我想出來的了 =,=
 首先是Betty定理：
 如果無理數alpha, beta滿足
 1. alpha, beta > 0
 2. 1/alpha + 1/beta = 1
 那么，序列{[alpha*n]}和{[beta*n]}構成自然數集的一個分劃，其中[]是取整函數
 
 這道題對應的alpha和beta分別是(1+sqrt(5))/2,(3+sqrt(5))/2，其實是一個黃金分割

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int x, y;
    double alpha = (1.0 + sqrt(5.0)) / 2.0;
    double beta = (3.0 + sqrt(5.0)) / 2.0;
    while (cin >> x >> y) {
        if (x > y) {
            int temp = x;
            x = y;
            y = temp;
        }
        int n = ceil(y / beta);
        int x1 = alpha * n;
        int y1 = beta * n;
        if (x == x1 && y == y1)
            cout << 0 << endl;
        else
            cout << 1 << endl;
    }
    return 0;
}