Solução

Para esse problema vamos primeiro achar uma recursão que represente o problema:

• $f_x = f_{x-1} + f_{x-2} + 1$
• $f_1 = 1$
• $f_0 = 1$

Pois para cada valor de fibonacci, temos que a quantidade de chamadas recursivas é igual a quantidade de $x-1$ mais $x-2$ mais o dele mesmo $1$.

Agora já poderíamos montar uma matriz 3x3 e resolver o problema com exponenciação rápida, porém podemos deixar o problema mais simples por meio de matemática.

Vamos partir da hipótese que $f_x = 2\cdot fib_x -1$:

Podemos verificar para os casos bases que isso é verdade:

• $f_0 = 2\cdot fib_0 - 1 \Rightarrow f_0 = 2\cdot 1 - 1 = 1$
• $f_1 = 2\cdot fib_1 - 1 \Rightarrow f_1 = 2\cdot 1 - 1 = 1$

Para o caso geral temos que:

$f_x = f_{x-1} + f_{x-2} + 1 \\ \Rightarrow f_x = (2\cdot fib_{x-1}-1) + (2\cdot fib_{x-2}-1) + 1\\ \Rightarrow f_x = 2 \cdot (fib_{x-1}+fib_{x-2}) - 1\\ \Rightarrow f_x = 2\cdot fib_x - 1$

Provando assim por indução que $f_x = 2\cdot fib_x - 1$.

Para calcular $fib_x$ podemos usar o fato que dado uma matriz $M = \left[{\begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} } \right]$, considerando $A = M^n$ sendo $n$ o $n$-ésimo número de Fibonacci, temos que $fib_n = A_{1,1} = (M^n)_{1,1}$.

Com isso podemos calcular $M^n$ usando a representação em binário de $n$, pois $M^n = M^{c_1 + c_2 + \ ...\ c_k} = M^{c_1}\cdot M^{c_2} \ ... \ M^{c_k}$ sendo $c_1$ as potências de dois que compôem $n$, com isso usando essa técnica podemos aplicar a mesma idéia em matrizes, e é claro computando sempre os elementos módulo $b$.

Código: