GeneralizedFibonacci | Topcoder Archive

Problem Statement

A generalized Fibonacci sequence modulo n is constructed in the following way: let f[0] = a, f[1] = b, for i > 1 let f[i] = (f[i - 1] + f[i - 2]) mod n. Here x mod n means the remainder of integer division of x by n, for example, 7 mod 3 = 1.

You are given ints a, b, n and v. Return the smallest i such that f[i] = v. If there is no such i, return -1.

Definition

Class:: GeneralizedFibonacci
Method:: earliest
Parameters:: int, int, int, int
Returns:: int
Method signature:: int earliest(int a, int b, int n, int v)
(be sure your method is public)

Constraints

n will be between 2 and 50, inclusive.
a will be between 0 and n - 1, inclusive.
b will be between 0 and n - 1, inclusive.
v will be between 0 and n - 1, inclusive.

Examples

```
1
```
```
1
```
```
5
```
```
3
```
```
Returns: 3
```
In this case the generalized Fibonacci sequence is 1, 1, 2, 3, 0, 3, etc. The first occurrence of 3 is at position 3.
```
1
```
```
1
```
```
5
```
```
4
```
```
Returns: 8
```
If we continue the sequence from the previous example, we get 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, etc. 4 occurs at position 8.
```
1
```
```
2
```
```
13
```
```
7
```
```
Returns: -1
```
7 never occurs in this generalized Fibonacci sequence.
```
0
```
```
1
```
```
2
```
```
0
```
```
Returns: 0
```
```
5
```
```
1
```
```
50
```
```
46
```
```
Returns: 182
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.