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 3×3 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:

https://gist.github.com/fredbr/f0b0fd76a454882cc691feedaeb62268