hdu 3117 斐波那契数列

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3117

只会求后四位的，前四位也是看别人的博客学的。。。。

http://blog.csdn.net/xieqinghuang/article/details/7789908

View Code

 1 #include<iostream>
 2 #include<cmath>
 3 const int m=10000;
 4 const double t=(1+sqrt(5.0))/2;
 5 using namespace std;
 6 int n;
 7 int f[40]={0,1,1,2,3,5,8,13,21,34,55};
 8 
 9 struct Matrix{
10     int map[2][2];
11 };
12 
13 Matrix mat;
14 
15 Matrix Mul(Matrix &a,Matrix &b){
16     Matrix c;
17     for(int i=0;i<2;i++){
18         for(int j=0;j<2;j++){
19             c.map[i][j]=0;
20             for(int k=0;k<2;k++){
21                 c.map[i][j]+=a.map[i][k]*b.map[k][j];
22                 c.map[i][j]%=m;
23             }
24         }
25     }
26     return c;
27 }
28 
29 Matrix Pow(int n){
30     if(n==1)return mat;
31     else if(n&1){
32         return Mul(mat,Pow(n-1));
33     }else {
34         Matrix temp=Pow(n>>1);
35         return Mul(temp,temp);
36     }
37 }
38 
39 int main(){
40     while(scanf("%d",&n)!=EOF){
41         if(n<40){
42             for(int i=11;i<40;i++){
43                 f[i]=f[i-1]+f[i-2];
44             }
45             printf("%d\n",f[n]);
46             continue;
47         }
48         mat.map[0][0]=1;
49         mat.map[0][1]=1;
50         mat.map[1][0]=1;
51         mat.map[1][1]=0;
52         mat=Pow(n);
53         double ans=log10(1.0/sqrt(5.0))+n*log10(t);
54         ans=ans-int(ans);//减去整数部分，得到小数
55         ans=pow(10.0,ans);
56         ans*=1000;
57         printf("%d...",(int)ans);
58         int temp=mat.map[0][1];
59         if(temp<10){
60             printf("000%d\n",temp);
61         }else if(temp<100){
62             printf("00%d\n",temp);
63         }else if(temp<1000){
64             printf("0%d\n",temp);
65         }else {
66             printf("%d\n",temp);
67         }
68     }
69     return 0;
70 }