Fibonacci
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4930 Accepted Submission(s): 2296
Problem 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
0
1
2
3
4
5
35
36
37
38
39
40
Sample Output
0
1
1
2
3
5
9227
1493
2415
3908
6324
1023
題目分析：
當N的值很大的時候就需要用到斐波那契數列的性質求解
（1）我們要知道斐波那契數列的通項公式：F[N]=(1/√5) * [((1+√5)/2)^N-((1-√5)/2)^N].
（2）對數log的強悍(以10為底)：對兩邊取對數
logF[N]=-0.5*log5+log [((1+√5)/2)^N-((1-√5)/2)^N].
我們知道當N小于21的時候，斐波那契的數值不超過四位，而當N超過21時，((1-√5)/2)^N的值已經趨向于0了，我們可以不管 這項。那麼原式就可以化為：
logF[N]=-0.5*log5+N*log (1+√5)/2
把後面的記為K=-0.5*log5+N*log (1+√5)/2
那麼 10^K=F[N];！！！
舉個例子： 10^2.3=199.5262314.......
10^0.3=1.995262314.......
這樣具體的數字很直覺，對映到 10^K=F[N]，取K的小數部分後，10^K就變為了科學計數的形式，那麼此時你要取多少位就可以取 多少位，就像要是你知道了10^0.3，那麼你想得到1.995262314......的幾位就幾位！！
#include<cstdio>
#include<cmath>
int main()
{
int n;
int f[30];
f[0] = 0;
f[1] = 1,f[2] = 1;
for(int i = 3; i < 21; i++)
f[i] = f[i-1] + f[i-2];
while(~scanf("%d",&n)){
if(n < 21)
printf("%d\n",f[n]);
else
{
double k = -0.5 * log10(5) + n * log10((1 + sqrt(5 * 1.0)) / 2);
k -= int(k);
double ans = pow(10,k);
while(ans < 1000)
{
ans *= 10;
}
printf("%d\n",(int)ans);
}
}
return 0;
}