题解 P2252 【取石子游戏】

· · 题解

推销blogQAQ：https://wenjing233.github.io/
自信的，我认为我的这篇题解事讲的最好的QAQ
给定两堆石子，每次可以在一堆或两堆中取任意个石子（至少1个）轮流取，取完的人嬴
网上看完了证明，感觉这题并不是很适合放在第二题，这里在书信息学奥赛数学一本通里放在第二题（实际上也只有两题）不大合适，并且书上并没有给出证明
定义当前状态为一个二元组(a,b)表示两组石子分别有a,b个
显然(a,b)等价于(b,a)
首先显然的(k,0)(0,k)(k,k)都是先手必胜态

定理1：对于a!=b的二元组(a,b)先手必败态对于不同的a只有一组

若存在(a,b)(a,c)（c>b）两组
则a,c一定能被取到a,b则先手是必胜的
同样这也能解释这个游戏为什么不是必胜就是必败

定理2：若有必败(a,b) (a+k,c+k)不存在

证明和上面同理

定理3：对必败的二元组(a,b)按a排序，则b[n]=a[n]+n-1;

若前k个二元组满足b-a=第几个-1 则第k+1个二元组也满足
假设(a[n],a[n]+n-1)是必胜态则他一定可以到其他必败态
若在左边取则到了已经有的a或b且差值变大，不是必胜态
若在右边取，则差值变小，小差值的二元组已经有了且开头不是a[n]
同时差值不变，但a变小，所以不存在必败态
所以二元组的通向式就得到了，然后就可以得到网上的式子了
但实际上我感觉这题做到递推式做出来就已经有蓝题难度了（
递推式是b=[a*1.618] ([]是下取整符号)
那么接下来涉及的东西就已经不属于博弈论了XD

贝亚蒂定理

设a、b是正无理数且 1/a +1/b =1。记P={ [na] | n为任意的正整数}，Q={ [nb] | n 为任意的正整数}，([x]'指的是取x的整数部分)则P与Q是Z+的一个划分，即P∩Q为空集且P∪Q为正整数集合N+。（这玩意儿总不用我证明了吧）
这里前面我们已经证明过a,b是不相等且不重复的二元组，则他们属于贝亚蒂列
那么接下来就事解方程时间辣QAQ
 已知Beatty序列：an= ⌊αn⌋，bn= ⌊βn⌋，而bn = an + n = ⌊αn⌋ + n = ⌊（α+1）n⌋，於是β = （α+1），代入1/α + 1/β = 1，解得α =（1+√5）/ 2 ≈ 1.618，這個數字就是黃金比例數！！
这段事最简单的，就粘别人blog了QAQ
没咯~~~

 #include <bits/stdc++.h>
const double L = 1.6180339887;
int main()
{
    long long a,b,det;
    while(cin>>a>>b)
    {
        if(a > b) swap(a,b);
        det = b-a;
        if(a == int(det * L))
            printf("0\n");
        else printf("1\n");
    }
    return 0;
}