石子 斐波那契
title: 题目
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".
输入有多组.每组第1行是2$<=n<2^{31}$. n=0退出.
title: input
2
13
10000
0
title: output
Second win
Second win
First win
title: 思路
不是基础的Nim游戏, 按照这个的思路试试：[[#石子-威佐夫博弈|石子 威佐夫博弈]]
必输态 1 2 3 5 8...
可以猜测是斐波那契数列, 即n为斐波那契数列的数时必输
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e2 + 10, M = 1e7, MOD = 1e9;
typedef long long LL;
LL n;
LL f[N];
int main()
{
f[1] = 1, f[2] = 1;
for (int i = 3; i <= 56; i++)
f[i] = f[i - 1] + f[i - 2];
while (cin >> n && n)
{
if ((*lower_bound(f, f + 56, n)) == n)
cout << "Second win\n";
else
cout << "First win\n";
}
return 0;
}