BZOJ 2275([Coci2010]HRPA-齊肯多夫定理-Fibonacci Nim)

2275: [Coci2010]HRPA
Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 63  Solved: 30
[Submit][Status]
Description
N個石子，A和B輪流取，A先。每個人每次最少取一個，最多不超過上一個人的個數的2倍。
取到最後一個石子的人勝出，如果A要有必勝策略，第一次他至少要取多少個。

Input
第一行給出數字N，N<=10^15.第二行N個數字

Output
如題

Sample Input
4
Sample Output
1
HINT

Source

[Submit][Status]


齊肯多夫(zeckendorf)定理：任何一正整數都能拆成一堆互不相同的正整數的和，且一定存在一種取法取到不超過它的最大Fib數.

而且根據（CCR推測）:如果n是Fib數那麼先取石子的人取不到最後那個（證明我Mo聽懂）

[cpp]
#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
#include<cmath>  
#include<cctype>  
#include<cassert>  
#include<climits>  
using namespace std; 
#define For(i,n) for(int i=1;i<=n;i++)  
#define Rep(i,n) for(int i=0;i<n;i++)  
#define Fork(i,k,n) for(int i=k;i<=n;i++)  
#define ForD(i,n) for(int i=n;i;i--)  
#define Forp(x) for(int p=pre[x];p;p=next[p])  
#define RepD(i,n) for(int i=n;i>=0;i--)  
#define MEM(a) memset(a,0,sizeof(a))  
#define MEMI(a) memset(a,127,sizeof(a))  
#define MEMi(a) memset(a,128,sizeof(a))  
#define INF (2139062143)  
#define F (1000000009)  
#define MAXN (10000+10)  
typedef long long ll; 
ll f[MAXN]; 
int main() 
{ 
//  freopen("bzoj2275.in","r",stdin);  
    //freopen(".out","w",stdout);  
    ll n; 
    cin>>n; 
    f[0]=f[1]=1; 
    int size=1; 
    while (f[size]<n) size++,f[size]=f[size-1]+f[size-2]; 
    if (f[size]==n) {cout<<n<<endl; return 0;} 
    while (n) 
    { 
        while (f[size]>n) size--; 
        if (f[size]==n)  
        { 
            cout<<f[size]<<endl;return 0; 
        } 
        n-=f[size]; 
    } 
     
         
    return 0; 
} 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXN (10000+10)
typedef long long ll;
ll f[MAXN];
int main()
{
// freopen("bzoj2275.in","r",stdin);
 //freopen(".out","w",stdout);
 ll n;
 cin>>n;
 f[0]=f[1]=1;
 int size=1;
 while (f[size]<n) size++,f[size]=f[size-1]+f[size-2];
 if (f[size]==n) {cout<<n<<endl; return 0;}
 while (n)
 {
  while (f[size]>n) size--;
  if (f[size]==n)
  {
   cout<<f[size]<<endl;return 0;
  }
  n-=f[size];
 }
 
  
 return 0;
}