hdu 1568 Fibonacci(Fibonacci通項公式)

題目：​​http://acm.hdu.edu.cn/showproblem.php?pid=1568​​

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

1

2

3

4

5

35

36

37

38

39

40

Sample Output

1

1

2

3

5

9227

1493

2415

3908

6324

1023

分析：x=1234567.求其前四位數： log10(x)=log10(1.234567)+6. 是以1.234567=10^(log10(x)-6). 1234 =(int) 10^(log10(x)-6)*1000. [6=length-4,length=(int)log10(x)+1]同時我們知道：

對于小于10000的數字可以存儲在數組中直接輸出，大于等于10000的數字則用上式計算。我們能知道：i<21 f[i]<1e4.當n=21時[(1-sqrt(5))/2]^n --> 0.618^n 0.618自乘5次就會退一個10進制等級。是以n>=21可以忽略[(1-sqrt(5))/2]^n。log10(x)=log10[ 1/sqrt(5)*[(1+sqrt(5))/2]^n ]=log10(1/sqrt(5))+n*log10(1+sqrt(5))/2). 

例如：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn=50; //,mod=1e4;
int f[maxn];
int main()
{
    f[0]=0;
    f[1]=1;
    for(int i=2;i<21;i++){
        f[i]=f[i-1]+f[i-2];  //i<21 f[i]<1e4.
    }
    int n;
    double q1=log10(1/sqrt(5)),q2=log10((1+sqrt(5))/2);
    while(cin>>n){
        if(n<21){   printf("%d\n",f[n]); continue; }
        double t=q1+n*q2;
        double p=t-(int)t;
        double ans1=pow(10,p);
        cout<<(int)(ans1*1000)<<endl;
    }
    return 0;
}