威佐夫博弈的逆天证明来喽

1. 游戏规则回顾

• 两堆石子，数量分别为 (a) 和 (b)，满足 (a $\leq$ b)。
• 两位玩家轮流操作，每次操作可以从一堆中取任意颗石子，或者从两堆中取同样多的石子。
• 无法操作的玩家输掉游戏。

2. 必败状态的定义

• 必败状态：当前玩家无论怎么操作，最终都会输掉游戏的状态。
• 必胜状态：当前玩家可以通过某种操作，将游戏状态转化为对方的必败状态，从而获胜。

3. 必败状态的性质

通过观察和归纳，我们发现一些必败状态：

• ((0, 0))
• ((1, 2))
• ((3, 5))
• ((4, 7))
• ((6, 10))

这些必败状态满足以下规律：

• 设第 (k) 个必败状态为 (($a_k$, $b_k$))，则 ($b_k$ = $a_k + k$)。
• ($a_k$) 是集合 ({$a_0$,$a_1$, $a_2$, $\ldots$}) 中最小未出现的整数。

4. 必败状态的证明

4.1 必败状态的后继状态不是必败状态

证明：

• 假设 (($a_k$, $b_k$)) 是一个必败状态，其中 ($b_k$ = $a_k + k$)。
• 从一堆中取石子：
  • 如果从 ($a_k$) 堆中取 (x) 个石子，变为 (($a_k - x$, $b_k$))。
  • 如果从 ($b_k$) 堆中取 (x) 个石子，变为 (($a_k$, $b_k - x$))。
  • 这些状态的差值 ($b_k$ - $a_k$) 不再等于 (k)，因此不可能是必败状态。
• 从两堆中取同样多的石子：
  • 如果从两堆中各取 (x) 个石子，变为 (($a_k - x$, $b_k - x$))。
  • 由于 ($b_k - a_k = k$)，新的差值 ($b_k - x - (a_k - x$) = k)，但 ($a_k - x$) 和 ($b_k - x$) 不满足 ($a_k$) 是最小未出现整数的性质，因此不可能是必败状态。

因此，必败状态的后继状态不可能是另一个必败状态。

4.2 必胜状态必有一个后继状态是必败状态

证明：

• 假设 ((a, b)) 是一个必胜状态，其中 (a $\leq$ b)。
• 如果 (a = 0)，则从 (b) 堆中取 (b) 个石子，变为 ((0, 0))，这是一个必败状态。
• 如果 (a > 0)：
  • 如果 (b = a + k)，其中 (k) 是某个整数：
    • 如果 (a) 是集合 ({$a_0$, $a_1$, $a_2$, $\ldots$}) 中的某个 ($a_i$)，则 ((a, b)) 本身是必败状态，矛盾。
    • 如果 (a) 不是集合中的某个 ($a_i$)，则存在某个 ($a_i$) 使得 ($a_i < a$) 且 ($a_i$) 是最小未出现整数。从 (a) 堆中取 ($a - a_i$) 个石子，变为 (($a_i, b - (a - a_i)$))，这是一个必败状态。
  • 如果 (b $\neq$ a + k)，则可以通过从 (b) 堆中取 (b - (a + k)) 个石子，变为 ((a, a + k))，这是一个必败状态。

因此，必胜状态必有一个后继状态是必败状态。

5. 必败状态的通项公式

根据上述规律，我们可以得出必败状态的通项公式：

• 设当前状态为 ((a, b))，其中 (a$\leq$ b)。
• 当 ($a=\left\lfloor (b - a)\times\phi \right\rfloor$) 时，该状态为必败状态，其中 ($\phi = \frac{1 + \sqrt{5}}{2}$) 是黄金分割比。

代码去看看别的题解里的吧，都看到这了要是就为了份代码就没意思了。