前置知识：齐肯多夫（Zeckendorf）定理
内容：任何正整数都可以表示成若干个不连续的斐波那契数之和，这种和式称为齐肯多夫表述法，构造这种和式可以通过每次贪心选出最大的不超过它的斐波那契数。
证明（这里只考虑 nnn 不为斐波那契数的情况）：
考虑数学归纳法，可以无脑得到1=1,2=2,3=3,4=1+3,5=2+3…1=1,2=2,3=3,4=1+3,5=2+3\dots1=1,2=2,3=3,4=1+3,5=2+3…
假设现在所有小于 nnn 的数都满足该定理，那么我们选择让 nnn 减去最大的不超过它的斐波那契数，显然新的 nnn 小于了旧的 nnn ，故满足，至于为什么不会选重斐波那契数见下文
构造证明
考虑我们依次取 Fibt1⩽n<Fibt1+1,Fibt2⩽n−Fibt1<Fibt2+1Fib_{t_1}\leqslant n<Fib_{t_1+1},Fib_{t_2}\leqslant n-Fib_{t_1}<Fib_{t_2+1}Fibt1 ⩽n<Fibt1 +1 ,Fibt2 ⩽n−Fibt1 <Fibt2 +1
显然，t1≠t2t_1\not=t_2t1 =t2 ，因为2Fibt1⩾Fibt1+Fibt1−1=Fibt1+1>n2Fib_{t_1}\geqslant Fib_{t_1}+Fib_{t_1-1}=Fib_{t_1+1}>n2Fibt1 ⩾Fibt1 +Fibt1 −1 =Fibt1 +1 >n
先看结论：
1.如果n为斐波那契数，则先手必输。
2.如果正整数 n 不为斐波那契数，则先手必赢。
证明：
1.先手不能一起全部取走，给后手的如果是一个斐波那契数，那么后手一定能给回来另一个斐波那契数，因为后手可以选择的数字的范围更大，久而久之先手一定会给后手一个非斐波那契数，然后看下一个证明
2.根据齐肯多夫定理，我们可以把n表示为 f1+f2+⋯+fkf_1+f_2+\dots+f_kf1 +f2 +⋯+fk 满足 ∀i，fi\forall i，f_i∀i，fi 为斐波那契数。f1<f2<⋯<fkf_1<f_2<\dots <f_kf1 <f2 <⋯<fk 。先手先取 f1f_1f1 ，显然后手没法一步取走 f2f_2f2 ，因为f2>2f1f_2>2f_1f2 >2f1 一定存在。我们假设先手足够聪明，那么先手一定可以通过拉扯来作为取走属于 f2f_2f2 的最后一个元素。同理我们对于每一个 fif_ifi 最后的一个元素都是先手取走的，所以最后是先手赢。
最后是代码：
