题目大意：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说的是否正确。



   解决方法：首先，要知道斐波那契数列的通项公式： 

                 F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}  
                接着，化简，在n足够大的时候，可以省去后面【(1-sqrt(5))/2】^n。
                那么式子就可以化为：
                An=1/sqrt(5)*[(1+sqrt(5))/2]^n;
               但题目要求的是An的前4位，而显然按照上面的公式，很快也就会超出int的范围，那么只能通过去对数来降低其长度。
               对等式两边取对数有： lgAn=n*lg((1+sqrt(5.0))*0.5)-0.5*lg(5.0);
               这里选取log10的原因是lg(n*10^m)=lg(n)+m; 而10^n就是答案mod 10^m,所以，我们只要将10^n乘到>1000即刻取出前4位
 1#include<iostream>
 2#include<cmath>
 3using namespace std;
 4int main()
 5{ int fib[21],i,n;
 6  fib[0]=0;fib[1]=1;
 7  for(i=2;i<21;i++)
 8  fib[i]=fib[i-1]+fib[i-2];
 9
10  while(scanf("%d",&n)!=EOF)
11  {
12     if(n<=20)
13       printf("%d\n",fib[n]);
14     else
15      { double p=n*log10((1+sqrt(5.0))*0.5)-0.5*log10(5.0);
16        p=p-int(p);
17        int res=pow(10.0,p)*1000;
18        printf("%d\n",res);
19      }
20}
21 return 0;
22}
23
。