rootn's blog

Relation in GCD and FIbonacci
By rootn, history, 5 years ago, In English

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

  • Vote: I like it
  • +46
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

link to the problem plz.

→ Reply
»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

I think that you could precompute the fibonacci numbers into an array and then create a segment tree with gcd operation in this array.

→ Reply