You are not logged in. Please login at www.codechef.com to post your questions!

×

HACKS - Editorial

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.

This question is marked "community wiki".

asked 21 Jan '18, 17:23

accelmage's gravatar image

4★accelmage
52
accept rate: 0%

edited 05 Feb '18, 13:57

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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