题解——P6487 [COCI2010-2011#4] HRPA
斐波那契数列
定义第 \(i\) 项为 \(Fib(i)\)，递推式：
\[Fib(i)=\begin{cases} 1&(i\le 2)\\ Fib(i-1)+Fib(i-2)&(i>2) \end{cases}\]斐波那契数列的前几项为 \(1,1,2,3,5,8,13,21,34,55,89\)。
齐肯多夫定理
对于任意一个正整数 \(n\)，都可以视为若干个不相邻的斐波那契数之和，即：
\[n=\sum_{i=1}^k Fib(t_i) \quad \forall i\in [1,k),t_i+1\ne t_{i+1} \]证明：
若 \(n\) 为斐波那契数，结论显然成立；
若 \(n\) 不为斐波那契数，我们找到一个小于 \(n\) 且最大的的斐波那契数 \(Fib(i)\)，用式子表示就是 \(Fib(i)
这样我们设 \(n'=n-Fib(i)\)，仿照上面找到一个 \(Fib(j)\)，使得 \(Fib(j)< n'< Fib(j+1)\)。
不断重复上面步骤即可证得拆分成立，下面我们来证明不相邻。
若存在一个 \(j+1=i\)，那么也就是 \(n\) 中可以选取到 \(Fib(i)\) 和 \(Fib(i-1)\)，二者之和为 \(Fib(i+1)\) 这样 \(n>Fib(i+1)\) 与我们“找到小于 \(n\) 且最大的一个斐波那契数”是相悖的，于是题设 \(j+1=i\) 不成立。
斐波那契博弈的胜败
斐波那契博弈指在一堆 \(n\) 个石子中，先手可以取 \([1,n-1]\) 个石子，接下来两人轮流取石子，石子的个数至少为 \(1\)，至多为上次对方所取石子数量的二倍，取到最后一个石子的一方获胜。
判定：当且仅当 \(n\) 为斐波那契数时，先手必败；否则先手必胜
（1）前置定理
定理 \(1\)：
\[\because Fib(i-1)定理 \(2\)：
\[\because Fib(i+1)定理 \(3\)：
\[\because Fib(i)（2）证明
我们用数学归纳法来证明“必败”的结论，设此时 \(n=Fib(k+1)\)，且对于 \(1\le k\) 的结论均成立。
我们将其拆分成 \(Fib(k-1)\) 和 \(Fib(k)\) 两堆，先考虑 \(Fib(k-1)\) 这一部分。
若先手取小于 \(\dfrac{Fib(k-1)}{3}\) 个石子，由定理 \(2\) 可知，可以将 \(Fib(k-1)\) 进一步拆分。
若取大于等于 \(\dfrac{Fib(k-1)}{3}\) 个石子，发现剩余的石子个数 \(x\le \dfrac{Fib(k-1)\times 2}{3}\)，与 \(\dfrac{Fib(k)}{2}\) 比较，通分后根据定理 \(3\) 可知，\(x\le \dfrac{Fib(k-1)\times 2}{3}<\dfrac{Fib(k)}{2}\)。
也就是说，取完左半部分后，\(2\times x
接着对于 \(n\) 不为斐波那契数时，我们按照上面的齐肯多夫定理，将 \(n\) 划分成若干堆大小为斐波那契数的石子，我们先手先全部取走最小的一堆，接着对于剩余每一个小堆，显然取到最后一个石子的是先手（可以理解成一个小堆就是一次交替，先后手不会改变），且由定理 \(1\) 可知，因为划分的斐波那契数不相邻，所以也不会出现下一堆可以由后手直接取完，于是到最后一个小堆时，后手必败。
解题
于是对于本题，先手要取的最小值就是划分后最小的斐波那契数，于是我们直接打表划分即可。
ll n;
ll fib[105]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657};
bool vis[105];
int main(){
n=read();
for(int i=74;i>=1;i--){
if(!vis[i+1]){
if(n