Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Relation in GCD and FIbonacci

Revision en1, by rootn, 2019-08-23 20:35:42

Recently, I encountered a problem where this relation in GCD and Fibonacci Numbers came in very handy.

Problem is, given an array of size n of positive integers and two non-negative integers l and r (0 <= l <= r < n). And we need to calculate gcd(fib(l), ...., fib(r)) where fib(i) is the ith fibonacci number.

Here, the relation that is very useful is gcd(fib(m), fib(n)) = fib(gcd(m, n)).

A more detailed description can be found here: https://www.math.hmc.edu/funfacts/ffiles/20004.5.shtml

Tags #math

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rootn 2019-08-23 20:35:42 589 Initial revision (published)