题解：P2252 [SHOI2002] 取石子游戏 |【模板】威佐夫博弈

· · 题解

题目传送门

问题分析

游戏规则： 有两堆石子，每次可以从一堆中取任意多石子，或从两堆中取相同数量的石子。

胜利条件：

取走最后一颗石子者获胜。

关键发现： 若满足以下条件不管怎么拿都会输。

1.若两堆石子数量为(a, b) 且 a \le b。

2.当且仅当 a = ⌊k\cdot \varphi⌋ , b = a + k 时，当前玩家必败。

3.其中 \varphi 是黄金比例 (\frac{\sqrt{5}+1}{2} \approx 1.618 ，k 是正整数）。

注意要用long double计算黄金分割比例。

Code：

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main() {
    int a, b;
    cin >> a >> b;

    if (a > b) swap(a, b);
    int k = b - a;

    // 计算 w = floor(k * phi)，其中 phi = (1+sqrt(5))/2。
    // 利用 phi 的性质：phi = 1 + 1/phi，且 w = (k * (sqrt(5) + 1)) / 2 的整数部分。
    // 用高精度计算避免误差。
    long double phi = (1.0L + sqrtl(5.0L)) / 2.0L;  // 用 long double 提高精度。
    long double k_phi = k * phi;
    int w = (int)k_phi;
    if (w == a && k_phi < w + 1.0L) {
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }

    return 0;
}