×

# HACKS - Editorial

Practice

Contest

Author: Timothy

Tester: Akshay Venkataramani

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.

This question is marked "community wiki".

52
accept rate: 0%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×3,766
×319
×137
×29
×3

question asked: 21 Jan '18, 17:23

question was seen: 369 times

last updated: 05 Feb '18, 13:57