### PROBLEM LINK:

**Author:** Timothy

**Tester:** Akshay Venkataramani

### DIFFICULTY:

EASY

### PREREQUISITES:

Math, GCD, Fibonacci

### EXPLANATION:

*The smallest number that can be obtained by substituting arbitrary values for x and y, in the equation ax+by=c is the GCD of a and b.*

The GCD can be calculated using Euclidean Algorithm or by using c++'s inbuilt function **__gcd()**.

But this isn’t enough to solve the problem. This is because of the constraint **0 ≤ i,j ≤ 10 ^{5}**. It is not possible to store any Fibonacci number after the 92

^{nd}one. This is where another property comes into play.

*The GCD of i^{th} and j^{th} Fibonacci numbers is the Fibonacci number whose position is the GCD of i and j.*

**GCD(Fib(i),Fib(j)) = Fib(GCD(i,j))**

This property holds only if Fibonacci series is 0-indexed.

### AUTHOR’S SOLUTION:

Author’s solution can be found here.