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 0indexed. AUTHOR'S SOLUTION:Author's solution can be found here.
This question is marked "community wiki".
asked 21 Jan '18, 17:23
