UVa Problem Solution: 10183 - How many fibs?

The close form of fibs does not help in the problem. The input range is too large that the precision of long double won't be sufficient to handle it correctly. Just generate all the fibs up to 100 digits and use string compare to find the bounds.

Code:

1. #include <algorithm>
2. #include <cmath>
3. #include <cstdio>
4. #include <cstring>
5. #include <deque>
6. #include <fstream>
7. #include <iostream>
8. #include <list>
9. #include <map>
10. #include <queue>
11. #include <set>
12. #include <stack>
13. #include <string>
14. #include <vector>
15. using namespace std;
16. struct bignum
17. {
18.   bignum(int v = 0) : start(max_digits)
19.   {
20.     bzero(digits, max_digits);
21.     assign(v);
22.   }
23.   bignum(char const *v) : start(max_digits)
24.   {
25.     bzero(digits, max_digits);
26.     assign(v);
27.   }
28.   void assign(int v)
29.   {
30.     start = max_digits;
31.     for (; v != 0; v /= 10) digits[--start] = v % 10; 
32.   }
33.   void assign(char const *v)
34.   {
35.     start = max_digits - strlen(v);
36.     for (int i = start; i < max_digits; ++i)
37.       digits[i] = *v++ - '0';
38.     remove_leading_zero();
39.   }
40.   void convert(int& v) const
41.   {
42.     v = 0;
43.     for (int i = start; i < max_digits; ++i, v *= 10) v += digits[i]; 
44.   }
45.   void convert(char *v) const
46.   {
47.     for (int i = start; i < max_digits; ++i)
48.       *v++ = digits[i] + '0';
49.     *v = '/0';
50.   }
51.   bignum& operator+=(bignum const& other)
52.   {
53.     start = min(start, other.start) - 1;
54.     for (int i = max_digits - 1, carry = 0; i >= start; --i) {
55.       int s = digits[i] + other.digits[i] + carry;
56.       digits[i] = s % 10;
57.       carry = s / 10;
58.     }
59.     remove_leading_zero();
60.     return *this;
61.   }
62.   bignum operator+(bignum const& other) const
63.   {
64.     bignum tmp(*this);
65.     tmp += other;
66.     return tmp;
67.   }
68.   bool operator<(bignum const& other) const
69.   {
70.     if (start > other.start) return true;
71.     else if (start < other.start) return false; 
72.     return memcmp(digits + start, other.digits + start, max_digits - start) < 0;
73.   }
74.   static int const max_digits = 500;
75.   char digits[max_digits];
76.   int start;
77. private:
78.   void remove_leading_zero()
79.   {
80.     for (; digits[start] == 0 && start < max_digits; ++start) {}
81.   } 
82. };
83. inline istream& operator>>(istream& is, bignum& n)
84. {
85.   char buf[bignum::max_digits+1];
86.   is >> buf;
87.   n.assign(buf);
88.   return is;
89. }
90. inline ostream& operator<<(ostream& os, bignum const& n)
91. {
92.   char buf[bignum::max_digits+1];
93.   n.convert(buf);
94.   os << buf;
95.   return os;
96. }
97. void gen_fibs(bignum *fibs, int nfibs)
98. {
99.   fibs[0] = 1;
100.   fibs[1] = 2;
101.   for (int i = 2; i < nfibs; ++i)
102.     fibs[i] = fibs[i-1] + fibs[i-2];
103. }
104. int main(int argc, char *argv[])
105. {
106. #ifndef ONLINE_JUDGE
107.   freopen((string(argv[0]) + ".in").c_str(), "r", stdin);
108.   freopen((string(argv[0]) + ".out").c_str(), "w", stdout);
109. #endif
110.   int const nfibs = 500;
111.   bignum fibs[nfibs];
112.   gen_fibs(fibs, nfibs);
113.   for (string s1, s2; cin >> s1 >> s2 && !(s1 == "0" && s2 == "0"); ) {
114.     bignum a(s1.c_str()), b(s2.c_str());
115.     int count;
116.     if (b < a) {
117.       count = 0;
118.     } else {
119.       bignum *first = lower_bound(fibs, fibs + nfibs, a);
120.       bignum *last = upper_bound(fibs, fibs + nfibs, b);
121.       count = last - first;
122.     }
123.     cout << count << '/n';
124.   }
125.   return 0;
126. }