#include <iostream>
#define N 100000
using namespace std;

int Fdata[N]={0,1,1,2};


int fib(int n)
{
    int tmp1,tmp2;//////用G++把这个放在全局变量里就会很诡异，tmp2会覆盖tmp2。
    if(n<N&&Fdata[n]!=0)
        return Fdata[n];
    if(n==0)
        return 0;
    if(n%2==0)
    {
        tmp1=(fib(n/2-1)+fib(n/2+1))*fib(n/2);
        tmp1%=10000;
    }
    else
    {
        tmp1=fib((n+1)/2);
        tmp2=fib((n-1)/2);
        if(tmp1==tmp2)
            cout<<"what!"<<endl;
        tmp1=tmp1*tmp1+tmp2*tmp2;
        tmp1%=10000;
    }
    if(n<N)Fdata[n]=tmp1;

    return tmp1;
}


int main()
{
    int n;
    while(cin>>n)
    {
        if(n==-1)break;
        cout<<fib(n)<<endl;
    }
    return 0;
}

• Re:这个是怎么回事啊？ (27) Serendo 2010-03-09 16:01:29
  • Re:这个是怎么回事啊？ (30) shinekai 2010-03-15 15:17:49