HDU1568大数取前4位

Time Limit: 1000MS

Memory Limit: 32768K

64bit IO Format: %I64d & %I64u

Description

2007年到来了。经过2006年一年的修炼，数学神童zouyu终于把0到100000000的Fibonacci数列
(f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2](i>=2))的值全部给背了下来。
接下来，CodeStar决定要考考他，于是每问他一个数字，他就要把答案说出来，不过有的数字太长了。所以规定超过4位的只要说出前4位就可以了，可是CodeStar自己又记不住。于是他决定编写一个程序来测验zouyu说的是否正确。

Input

输入若干数字n(0 <= n <= 100000000)，每个数字一行。读到文件尾。

Output

输出f[n]的前4个数字（若不足4个数字，就全部输出）。

Sample Input

Sample Output

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;
}