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

×

FIBEQN - Editorial

FIBEQN Editorial by Satwant Rana

The problem asks us to calculate $\sum_{i = 0}^n{F_i\ k^i}$, and time limit suggests we need to do it in $O(log\ N)$ time.

The model solution makes use of the fact that $F_i = \frac{\phi^i - \psi^i}{\phi-\psi}$, where $\phi = \frac{1 + \sqrt5}{2}$ and $\psi = \frac{1 - \sqrt5}{2}$. Leveraging this fact we can perform computations in $\mathbb Z[\sqrt5]$.

So the problem asks us to calculate $\sum_{i = 0}^n{\frac{\phi^i - \psi^i}{\phi-\psi}\ k^i} = \frac{\frac{(\phi\ k)^i - 1}{\phi - 1} - \frac{(\psi\ k)^i - 1}{\psi - 1}}{\phi - \psi}$. This can be done in $O(log N)$ time with logarithmic exponentiation in $\mathbb Z[\sqrt5]$.

Setter's Solution

This question is marked "community wiki".

asked 01 Apr '16, 00:19

harrypotter192's gravatar image

6★harrypotter192
115
accept rate: 0%

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:

×14,435
×251
×132
×43
×23

question asked: 01 Apr '16, 00:19

question was seen: 943 times

last updated: 01 Apr '16, 00:19