# UVa 10183

## Summary

A pretty ordinary BigNum problem.

## Explanation

Generate the Fibonacci sequence until the last number generated exceeds ${\displaystyle 10^{100}}$ and store it an array. It ends up taking about 480 numbers.

## Gotcha's

The first number input may be 0. Note that the problem defines a fairly non-standard sequence, where the first two numbers in the sequence aren't both 1, but rather 1 and 2.

## Notes

The Fibonacci numbers increase by approximately a factor of ${\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618}$. Thus, there are O(d) Fibonacci numbers with less than or equal to d digits. The exact constant multiple hidden by the O is ${\displaystyle {\frac {\log(10)}{\log(\phi )}}\approx 4.785}$. This would predict that we would need 478 numbers to store the Fibonacci numbers with less than 100 digits, when we actually used 480.

## Optimizations

Since we never have to through more than 500 numbers, and the size of the numbers, about 100 digits, is near the size of the sequence itself, a linear search or two find the correct lower and upper indices in the sequence is sufficient to pass the time limit. However, a binary search will yield a lower time.

## Input

0 1
1 1
10 100
1234567890 9876543210
0 0


## Output

1
1
5
4