hdu 1316 How Many Fibs?

How Many Fibs?

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5638 Accepted Submission(s): 2183

Problem Description

Recall the definition of the Fibonacci numbers:
f1 := 1
f2 := 2
fn := fn-1 + fn-2 (n >= 3)

Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a, b].

Input

The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a = b = 0. Otherwise, a <= b <= 10^100. The numbers a and b are given with no superfluous leading zeros.

Output

For each test case output on a single line the number of Fibonacci numbers fi with a <= fi <= b.

Sample Input

10 100

1234567890 9876543210

0 0

Sample Output

Source

University of Ulm Local Contest 2000

Recommend

Eddy | We have carefully selected several similar problems for you: 1753 1063 1047 1715 1147

大数问题，不是很难，不过处理起来有点繁琐，需要仔细一点。

题意：给定范围[a,b]（a<=b<=10^100），求在这范围内的斐波那契数有多少个。

附上代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 char ch[1005][500];
 6 int f1[500];
 7 int f2[500];
 8 void init()  //高精度加法初始化斐波那契数ch[]
 9 {
10     int i,j;
11     strcpy(ch[0],"1");
12     strcpy(ch[1],"1");
13     for(i=2; i<=1000; i++)
14     {
15         int n1=strlen(ch[i-2]);
16         int n2=strlen(ch[i-1]);
17         memset(f1,0,sizeof(f1));
18         memset(f2,0,sizeof(f2));
19         for(j=n1-1; j>=0; j--) f1[j]=ch[i-2][n1-j-1]-'0';
20         for(j=n2-1; j>=0; j--) f2[j]=ch[i-1][n2-j-1]-'0';
21         int c=0;
22         j=0;
23         while(j<=max(n1,n2))
24         {
25             f1[j]=f1[j]+f2[j]+c;
26             if(f1[j]>=10)
27             {
28                 f1[j]-=10;
29                 c=1;
30             }
31             else c=0;
32             j++;
33         }
34         int w=max(n1,n2);
35         while(!f1[w]) w--;     //去掉后面多余的0
36         for(j=w; j>=0; j--)
37             ch[i][j]=f1[w-j]+'0';
38     }
39 }
40 int main()
41 {
42     init();
43     int k,flag,i,j;
44     char str1[105],str2[105];
45     while(~scanf("%s%s",str1,str2)&&(strcmp(str1,"0")||strcmp(str2,"0")))
46     {
47         int n1=strlen(str1),n2=strlen(str2);
48         if(n1==n2) flag=1;
49         else flag=0;
50         k=0;
51         for(i=1; i<=1000; i++)
52         {
53             int n=strlen(ch[i]);
54             if(flag)       //当str1和str2的长度一样时
55             {
56                 if(n==n1&&strcmp(ch[i],str1)>=0&&strcmp(ch[i],str2)<=0) k++;
57                 if(n>n1||n==n1&&strcmp(ch[i],str2)>0) break;
58                 continue;
59             }
60             if(n>n2||n==n2&&strcmp(ch[i],str2)>0) break;   //当str1和str2的长度不一样时
61             if(n>n1&&n<n2)
62             {
63                 k++;
64                 continue;
65             }
66             if(n==n1&&strcmp(ch[i],str1)>=0) k++;
67             if(n==n2&&strcmp(ch[i],str2)<=0) k++;
68         }
69         printf("%d
",k);
70     }
71     return 0;
72 }