Problem Description

2007年到來了。經(jīng)過2006年一年的修煉，數(shù)學神童zouyu終于把0到100000000的Fibonacci數(shù)列(f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2] (i>=2) )的值全部給背了下來。接下來，CodeStar決定要考考他，于是每問他一個數(shù)字，他就要把答案說出來，不過有的數(shù)字太長了。所以規(guī)定超過4位的只要說出前4位就可以了，可是CodeStar自己又記不住。于是他決定編寫一個程序來測驗zouyu說的是否正確。

Input

輸入若干數(shù)字n(0 <= n <= 100000000)，每個數(shù)字一行。讀到文件尾。

Output

輸出f[n]的前4個數(shù)字（若不足4個數(shù)字，就全部輸出）。

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

分析

需要數(shù)學知識，整理分析轉自多個博客。當一個數(shù)非常大時，如何求出其前幾位如果是給定一個特定的數(shù)，當然可以逐步取出每一位即可。如a得個位，a/10得百位，a/10/10得千位。但是，當求x^y的前幾位時怎么辦呢？若x，y都非常大，則顯然很難解決：也許可以用大數(shù)乘法，暴力求解，結果自然是既占內存，又耗時間。還有，此題斐波拉契數(shù)列的前幾位，顯然求出每個斐波拉契數(shù)是不現(xiàn)實的。因此，可以采用取對數(shù)的方法來解決。

先看對數(shù)的性質,loga(b^c)=cloga(b),loga(bc)=loga(b)+loga(c);
假設給出一個數(shù)10234432,那么log10(10234432)=log10(1.023443210^7)=log10(1.0234432)+7
log10(1.0234432)就是log10(10234432)的小數(shù)部分.
log10(1.0234432)=0.010063744
10^0.010063744=1.023443198，
要求該數(shù)的前4位，則將1.0234431981000即可。
因此，pow(10.0,x的小數(shù)部分)即可方便求出x的前幾位。
求一數(shù)的前4位的對數(shù)方法可以表述為：

double x,temp;
while(scanf("%lf",&x)!=EOF)
{
  temp=log(x)/log(10.0);
  temp=temp-floor(temp); //floor(temp)函數(shù)求出小于temp的最大整數(shù)
  temp=pow(10.0,temp);
  while(temp<1000)
  temp*=10;
  //printf("%.0lf\n",temp); //采用浮點表達法時會四舍五入
  printf("%d\n",(int)temp);//此處不需四舍五入，直接舍棄后面的位
}

以下為斐波拉契數(shù)列的通項公式。
F(n)=（1/√5）[（（1+√5）/2）^{n-（（1-√5）/2）}n]（n=1，2，3.....）
改變通項的形式
F(n)=（1/√5）[（（1+√5）/2）^{n-（（1-√5）/2）}n]（n=1，2，3.....）
=(1/√5)[((1+√5)/2)^n(1-((1-√5)/(1+√5))^n）]（n=1，23.....）
即F(n)的各項可以由以上通項公式求得，而不是采用迭代。
對變化后的通項取對數(shù)，則得下式：
log10（F(n)）=-0.5log10（5.0）+（（double）n）log（f）/log（10.0）+log10（1-（（1-√5）/（1+√5））^n）
其中第三部分非常小，當n很大時趨近于0，可以忽略掉。
然后再單獨計算前20個數(shù)，不超過4位，可以單獨輸出。
C代碼如下，已通過：

#include "stdio.h"
#include "math.h"
int main()
{
  int n,i;
  int f[21]={0,1};
  for(i=2;i < 21;i++)
    f[i]=f[i-1]+f[i-2];
  double s=(sqrt(5.0)+1.0)/2.0;
  while(scanf("%d",&n) != EOF)
  {
    if(n<21)
    {
      printf("%d\n",f[n]);
      continue;
    }
    double ans=-0.5*log(5.0)/log(10.0)+(double)n*log(s)/log(10.0);
    ans-=floor(ans);
    ans=pow(10.0,ans);
    while(ans < 1000)
    ans *= 10;
    printf("%d\n",(int)ans);
  }
}