×

# 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".

115
accept rate: 0%

 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:

×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