FIBEQN Editorial by Satwant RanaThe 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]$.
This question is marked "community wiki".
asked 01 Apr '16, 00:19
