poj1067 取石子游戏 威佐夫博弈

题目

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，

一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。

现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

输入a，b，获胜输出1/失败输出0

思路&结论

n > m时，当且仅当m = [(a - b) * (sqrt(5) + 1) / 2] 时，先手必败 ,否则先手必胜

代码

int n,m,k;void solve()
{while(cin >> n >> m){if (n < m) swap(n,m);//n >= mk = n - m;int x = (int)(k * (sqrt(5) + 1) / 2);if (m == x) cout << 0 << endl;else cout << 1 << endl;}
}