题解：P6487 [COCI 2010/2011 #4] HRPA | 斐波那契博弈

· · 题解

斐波那契博弈模版题。用 f_i 来表示第 i 个斐波那契数（f_1=f_2=1，对于 i\ge3，f_i=f_{i-1}+f_{i-2}）。

引理 1：

当 n 为斐波那契数时，若先手不一次取完，则后手可以取到最后一块石子。

证明：

设 n=f_i。由 n\ge2，i\ge3。

若 i=3,4，即 n=2,3 时，显然后手必胜。

假设命题对任何小于 i 的正整数都成立（i\ge5）。下证命题对 i 也成立。

设先手第一次取走 k 个石子。那么：

综上所述，由第二数学归纳法，原命题成立。

引理 2：

齐肯多夫定理。任何正整数 n 都可以表示成除 f_1=1 外的若干个不连续的斐波那契数之和。这样的和式被称为“齐肯多夫表述法”。

证明：

当 n=1,2,3 时，由 f_2=1,f_3=2,f_4=3，命题成立。

假设命题对任何小于 n 的正整数数都成立（n\ge4）。下证命题对 n 也成立。

综上所述，由第二数学归纳法，齐肯多夫定理对任何正整数 n 都成立。

引理 3：

对于一个整数 x\ge2，设 i 是满足 f_i\ge x 的最小正整数。对于任意 k\ge i+2 都有 2x<f_k。

证明：2x\le2f_i<f_i+f_{i+1}=f_{i+2}\le f_k。

由引理 2（齐肯多夫定理），将 n 块石子分为若干堆，其中每一堆石子的个数递增且均为不连续的斐波那契数。

对于较大的 n-1 堆，由引理 1，只要后手 Slavko 先取且不一次取完，先手 Mirko 一定可以取到该堆的最后一块石子。

因此 Mirko 只需先手取完第一堆即可。由引理 3，由于 Mirko 每一堆最后一次取的数量小于该堆数量，所以 Slavko 一定无法直接取完下一堆。那么下一堆仍由 Slavko 先取且无法一次取完。于是 Mirko 一定能取到最大的一堆石子的最后一块，即这 n 块石子的最后一块。

因此本题答案即为用齐肯多夫表述法表示 n 后最少的一堆石子的数量。

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

int main(){
    long long n;cin>>n;long long lst=0;
    while(n>0){
        long long a=0,b=1,c=1;//f_0,f_1,f_2
        while(c<=n){
            c=a+b;
            a=b;b=c;
        }
        n-=a;lst=a;
    }
    cout<<lst;
    return 0;
}

代码中用到了每次取出最大的不大于 n 的斐波那契数组成的式子一定是 n 的齐肯多夫表述法的结论。这个结论可以用反证法证明。假设取出的数中存在连续的斐波那契数，设其中最大的为 f_i 和 f_{i+1}，那么一定没有取出 f_{i+2}（否则与“最大”矛盾）。又 n>f_i+f_{i+1}=f_{i+2}，因此一定选出了 f_{i+2}。矛盾。即证。