0
1
1
2
3
5
9227
1493
2415
3908
6324
1023
/**//*
pow尽量少用，减少精度损失。fibonacci通项F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
遇到N^n、a^n、a!之类的大数表达前几位，可利用科学计数法a^n=10^x=10^z*10^f,10的小数部分0<f<1,0<10^f<10,故为dig.ddd*10^z即科学计数法表示
*/
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define N 1000
int f[N];
int output(int n)
{
if(n<30&&f[n]<9999)return f[n];
double ans,f,tmp,cst=sqrt(5.0);//genhao5pow(5.0,0.5)
int z;
//tmp=pow((cst+1)/2,n+0.0)/cst;
//tmp=pow(long double((cst+1)/2+0.0),long double(n+0.0))/cst;
tmp=n*log10((cst+1)/2)-0.5*log10(5.0);
//z=floor(log10(tmp));
z=floor(tmp);
//f=log10(tmp)-z;
f=tmp-z;
ans=pow(10.0,f);
//ans=pow(long double(10.0),long double(f));
return int(1000*ans);
}
int main()
{
int n,i,j;
f[0]=0;
f[1]=1;
for(i=2;i<N;++i)
f[i] = f[i-1]+f[i-2];
#include<iostream>
#include<cmath>
using namespace std;
typedef int LL;
LL num[93]={ 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,
6765,1094,1771,2865,4636,7502,1213,1964,3178,5142,8320,1346,2178,3524,5702,9227,
1493,2415,3908,6324,1023,1655,2679,4334,7014,1134,1836,2971,4807,7778,1258,2036,
3295,5331,8626,1395,2258,3654,5912,9567,1548,2504,4052,6557,1061,1716,2777,4494,
7272,1176,1903,3080,4984,8065,1304,2111,3416,5527,8944,1447,2341,3788,6130,9919,
1605,2596,4201,6798,1100,1779,2880,4660,7540 };
int main( )
{
LL n;
double x,k=(1+sqrt(5.0))/2;
while( scanf("%d",&n) != EOF )
{
if( n<=92 )printf("%d\n",num[n]);
else
{
x=n*log10(k)-0.5*log10(5.0);
x=x-(int)x;
x=pow( 10.0, x );
n=(int)(x*1000);
printf("%d\n",n);
}
}
return 0;
} while(scanf("%d",&n)==1)
printf("%d\n",output(n));
return 0;
}