题解 P2252 【取石子游戏】

· · 题解

//我有关于黄金比的证明，求过。

威佐夫博奕

题目

有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利

首先我们规定: 后手必胜态被称为奇异局势，(0,0)

想一下(0,0)的下一个奇异局势是什么？

(2,1)

  1. 如果先手取走“1”中的1个，那么后手就从“2”中取出2个，此时取完，所以后手胜利。

  2. 如果先手取走“2”中的2个，那么后手取走“1”中的1个，此时取完，后手胜利。

  3. 如果先手取走“2”中的1个，那么后手就在两堆中各取走1个，此时取完，后手胜利。

  4. 如果先手在“1”和“2”各取走了1个，那么后手取走“2”中的1个，此时取完，后手胜利。

再下来是什么？

0: (0,0) 1: (1,2) 2: (3,5) 3: (4,7) 4: (6,10) 5: (8,13)

我们发现，第i个奇异局势的差值是i

我们发现，每一个状态的第一个都是以前没有出现过的最小非法整数。

证明：

假设第k个局势为(x, k + x)

如果先手缩小差值,后手可以变成先前的局势，然后死了，所以先手不会着么做。

如果x是之前已经出现过的数， 那么先手肯定可以缩小，取到与x匹配的奇异局势，后手死了。

如果x比mex大，可以两堆缩小成x = mex，然后后手又死了。

所以当且仅当x = mex时(x, k + x)为奇异局势。

显然地，全体正整数被奇异局势分割成两个不相交的集合。

乱搞之中，我们想到了beatty定理。

设a、b是正无理数且 \frac{1}{a} + \frac{1}{b} = 1。记P={ \lfloor na \rfloor | n为任意的正整数}，Q={ \lfloor nb \rfloor | n 为任意的正整数}，([x]'指的是取x的整数部分)则P与Q是Z+的一个划分，即P∩Q为空集且P∪Q为正整数集合N+。

证略（不等式）。

我们发现，相邻奇异局势的第一个数的差值是1或2,但分布过于玄学，所以我们可以认为第一个数被表示成\lfloor an \rfloor，n为任意正整数，a为一无理数。

这样，第二个数可以被表示为\lfloor (a + 1) n \rfloor（已证）

根据beatty定理，\frac{1}{a} + \frac{1}{a + 1} = 1

解：

\frac{1}{a} + \frac{1}{a + 1} = 1 a^2 - a - 1= 0 \Delta = 5 a _ 1 = \frac{1 + \sqrt{\Delta}}{2}, a _ 2 = \frac{1 - \sqrt{\Delta}}{2}

因为，a > 1；

我们取a = \frac{1 + \sqrt{5}}{2}

所以第k奇异局势的第一个数是\lfloor a k\rfloor

所以，如果这是一个奇异局势，那么第一个数是两数差值乘黄金比下取整。

#include<bits/stdc++.h>
using namespace std;

int n, m;

const double lorry = (sqrt(5.0) + 1.0) / 2.0;

int main() {
    cin >> n >> m;
    if(n < m) swap(n, m);
    int a = n - m;
    if(m == int(lorry * (double)a))
        cout << 0 << endl;
    else 
        cout << 1 << endl;
}