Sea

$${\displaystyle F_n=\left[\begin{array}{c}F(n)\\ F(n+1)\end{array}\right]}$$

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=\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]}$$

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}=\left[\begin{array}{cc}-1& 1\\ 1& 0\end{array}\right]}$$

Y en efecto se cumple:

$${\displaystyle C\times C^{-1}=\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]\times \left[\begin{array}{cc}-1& 1\\ 1& 0\end{array}\right]=\left[\begin{array}{cc}0(-1)+1\cdot 1& 0\cdot 1+1\cdot 0\\ 1(-1)+1\cdot 1& 1\cdot 1+1\cdot 0\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]=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 =C^{jq+i}\times F_0}$$ $${\displaystyle =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)$