bzoj 2275: [Coci2010]HRPA

据说叫斐波那契博弈。

先手最少取的石子数是把n用斐波那契数列拆分后最小的数。

原题+证明：

http://blog.****.net/acm_cxlove/article/details/7835016

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll f[100];
int main()
{
	scanf("%lld",&n);
	f[0]=f[1]=1;int i;
	for(i=2;;i++)
	{
		f[i]=f[i-1]+f[i-2];
		if(f[i]>=n)break;
	}
	for(;;i--)
	{
		if(n==f[i])
		{
			printf("%lld\n",n);
			return 0;
		}
		if(n>f[i])n-=f[i];
	}
	return 0;
}