How Many Fibs?
 
  
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3804    Accepted Submission(s): 1498 

  
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 
  
 
  
 
   

     5 4 
   
 
  
 
  
 
   
 1 #include <cstdio>

 2 #include <cstring>

 3 #include <cstdlib>

 4 #include <vector>

 5 #include <cmath>

 6 #include <iostream>

 7 #include <algorithm>

 8 #include <string>

 9 #include <map>

10 using namespace std;

11 const int maxn=500;

12 const int base=1000000;

13 const int INF=99999999;

14 const int MIN=-INF;

15 char a[maxn][500];

16 char* add(char*a,char*b)//    

17 {

18     int lena=strlen(a);

19     int lenb=strlen(b);

20     int i,j,k;

21     char c[500];

22     if(lena<lenb)

23     {

24         strcpy(c,a);

25         strcpy(a,b);

26         strcpy(b,c);

27     }

28     int A[500]= {0},B[500]= {0};

29     for(j=0,i=lena-1; i>=0; i--,j++)

30         A[j]=a[i]-'0';

31     int lenA=j;

32     for(i=lenb-1,j=0; i>=0; i--,j++)

33         B[j]=b[i]-'0';

34     int lenB=j;

35     for(i=0; i<lenB; i++)

36         A[i]+=B[i];

37     for(i=0; i<500; i++)

38     {

39         if(A[i]>9)

40         {

41             A[i+1]+=A[i]/10;

42             A[i]%=10;

43         }

44     }

45     for(i=500-1; i>=0; i--)if(A[i]!=0)break;

46     for(j=0; i>=0; i--)

47         c[j++]=A[i]+'0';

48     c[j]='\0';

49     return c;

50 }

51 int comper(char*a,char*b)//           0    1    -1

52 {

53     int lena=strlen(a);

54     int lenb=strlen(b);

55     if(lena>lenb)

56         return 1;

57     else if(lena<lenb)

58         return -1;

59     else if(lena==lenb)

60     {

61         for(int i=0; i<lena; i++)

62             if(a[i]<b[i])

63                 return -1;

64             else if(a[i]>b[i])

65                 return 1;

66     }

67     return 0;

68 

69 

70 }

71 int main()

72 {

73     int n,m,i,j,k,t;

74     a[1][0]='1';

75     a[2][0]='2';

76     for(i=3; i<=maxn; i++)

77     {

78         strcpy(a[i],add(a[i-1],a[i-2]));

79     }

80     //for(i=1;i<50;i++)

81     //  cout<<a[i]<<endl;

82 

83     char a1[maxn],b1[maxn];

84     while(cin>>a1>>b1)

85     {

86         int lena1=strlen(a1);

87         int lenb1=strlen(b1);

88         if(lena1==1&&lenb1==1&&a1[0]=='0'&&b1[0]=='0')return 0;

89         int cnt=0;

90         for(i=1; i<maxn; i++)

91         {

92             if(comper(a[i],a1)>=0&&comper(a[i],b1)<=0)

93                 cnt++;

94         }

95         cout<<cnt<<endl;

96     }

97 

98     return 0;

99 }