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 ≤ 105. It is not possible to store any Fibonacci number after the 92nd one. This is where another property comes into play.
The GCD of ith and jth 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.