HACKS - Editorial

easy
editorial
fibonacci
gcd
hacks
popc2018

#1

PROBLEM LINK:

Practice

Contest

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.