Sea

$$\displaystyle F_n = \begin{bmatrix} F(n) \\ F(n+1) \\ \end{bmatrix} $$

El vector que representa un par arbitrario de elementos consecutivos de Fibonacci.

Y sea ~C~ una matriz que cumple: ~C \times F_n = F_{n+1}~

En otras palabras, al multiplicar (por la izquierda) al vector, resulta el siguiente par consecutivo de Fibonacci, la matriz que cumple esto es:

$$\displaystyle C = \begin{bmatrix} 0& 1 \\ 1& 1 \\ \end{bmatrix} $$

Tambien existe una matriz ~C^{-1}~ tal que: ~C \times C^{-1} = C^{-1}\times C = I~

Donde ~I~ es la matriz identidad.

La matriz que cumple esto es: $$\displaystyle C^{-1} = \begin{bmatrix} -1& 1\\ 1& 0 \end{bmatrix} $$

Y en efecto se cumple:

$$\displaystyle C \times C^{-1} = \begin{bmatrix} 0& 1\\ 1& 1 \end{bmatrix} \times \begin{bmatrix} -1& 1\\ 1& 0 \end{bmatrix} = \begin{bmatrix} 0 (-1) + 1\cdot 1& 0\cdot 1 + 1\cdot 0 \\ 1(-1)+1\cdot 1& 1\cdot 1 + 1\cdot 0 \end{bmatrix} = \begin{bmatrix} 1& 0\\ 0& 1 \end{bmatrix} = I_2 $$

Se puede demostrar también que ~(C^k)^{-1} = (C^{-1})^k~

Entonces, supongamos que la solución a el problema, la cual llamaremos ~n~ (se asegura que la solución es menor o igual que ~10^9+6~) se puede escribir de la siguiente forma: $$\displaystyle n = i+jq$$ Donde ~i, j, q~ son enteros no negativos arbitrarios.

Y sabemos que ~F_n = C^n \times F_0~

La solución la podemos escribir como:

$$\displaystyle F_n = C^{i+jq} \times F_0$$ $$\displaystyle \quad = C^{jq+i} \times F_0$$ $$\displaystyle \quad = C^{jq} \times C^{i} \times F_0$$

(Multiplicamos a la izquierda ambos miembros por ~(C^{jq})^{-1}~)

$$\displaystyle (C^{jq})^{-1} \times F_n = I \times C^i \times F_0$$ $$\displaystyle (C^{jq})^{-1} \times F_n = C_i \times F_0$$ $$\displaystyle (C^{-1})^{jq} \times F_n = C_i \times F_0$$ $$\displaystyle (C^{-1})^{jq} \times F_n = F_i$$

Utilizando esto podemos fijar ~q~ a un entero lo suficientemente grande y memoizar en un mapa todos los números de Fibonacci hasta ~q~ junto con su índice, en cada consulta solo quedaría iterar desde ~j=0~ hasta ~\frac {10^9+6} {q}~ y calcular el lado izquierdo de la ecuación usando exponenciación binaria, si existe en el mapa, la solución es ~n=\text{mapa[lhs]} + j\cdot q~

Complejidad de preprocesar (usando un mapa ordenado) ~O(q \log q)~

Complejidad de cada consulta ~O((n/q) \log^2 q)~ (lo cual es asintótico con ~O(n \log^2 q)~, pero deja más claro que la constante no es muy grande)

Nos queda una complejidad temporal: ~O(q\log q + t\cdot(n/q)\cdot \log^2 q)~

Y si hacemos ~q=\sqrt n~

Nos queda: ~O(t\cdot \sqrt{n} \cdot \log^2 n)~

Ejercicio para el lector:

Resolverlo en ~O(t \cdot \sqrt[3]{n} \cdot \log n)~