Primeiro ponto, precisamos conhecer o comportamento da função para calcular Fibonacci de um número. Temos diversas alternativas. Primeiro, começar pela definição recursiva da função de Fibonacci:

<!-- language-all: lang-python -->

    def fib(n):
      if n == 1 or n == 2:
        return 1
      else:
        return fib(n-1) + fib(n-2)

Se você analizar a fundo, vai perceber que a única opção de um valor ser acrescentado ao número de retorno é quando temos na recursão a chamada para `fib(1)` ou `fib(2)`. Mas, e quantas chamadas de função são feitas ao todo? Para responder a essa pergunta, criei uma função que batizei de `meta_fib`. Além de contar as mesmas chamadas de função do retorno de Fibonacci, também adiciono um a cada chamada recursiva. Então, `meta_fib` é descrita como:


    def meta_fib(n):
      if n == 1 or n == 2:
        return 1
      else:
        return 1 + meta_fib(n - 1) + meta_fib(n - 2)
    		
`meta_fib(i)`, então, vai retornar quantas chamadas de função são feitas. [Resolvi comparar o quanto `meta_fib` crescia em comparação a `fib`](https://ideone.com/4kfNI6). Então, aparentemente, `meta_fib(a) = 2*fib(a) - 1`. Só que a função de Fibonacci tem crescimento exponencial. O @Ricardo Ribeiro colocou a fórmula em [sua reposta](https://pt.stackoverflow.com/a/294705/64969) (retornaremos a ela mais tarde):

[![fórmula de Fibonacci][1]][1]

Então, a quantidade de chamadas à função `fib` é:

[![quantas chamadas recursivas são feitas para calcular fib?][2]][2]

Ok, temos uma estratégia. Olhemos o enunciado para saber se a estratégia pode ser minimamente viável. Talvez com algumas dezenas de milhões de operações eu consiga fazer o cálculo com sucesso... note que (1 - φ) é um valor entre 0 e 1, portanto elevar ele a um número deixará ele mais próximo de zero.

> [...] Sua tarefa é simples, calcular o valor do resto de Fib( Fib( N ) ) por M.

> ###Entrada

> A entrada é composta por vários casos de teste e termina com EOF. Cada caso de teste consiste de uma linha com dois inteiros N e M (1 ≤ N ≤ 10<sup>9</sup>, 2 ≤ M ≤ 10<sup>6</sup>).

É... eles pedem para calcular até 1 bilhão... Creio que φ<sup>10<sup>9</sup></sup> é um pouco maior do que meu limite imaginário de alguns milhões de operações...

E se eu fizer com [memoização](https://pt.stackoverflow.com/q/175412/64969)? Bem, com isso eu garanto que eu não desço recursivamente duas vezes pelo mesmo `fib(n)`. Com memoização, calcular `fib(n + 2)` fica mais ou menos assim (colocar com `*` os valores memoizados):

    fib(n + 2) =
    fib(n + 1) + fib(n)* =
    fib(n)* + fib(n)* + fib(n - 1)*

E, nesse cálculo, os valores e `fib(n + 1)` e `fib(n + 2)` são memoizados ao serem calculados. E o quanto de memória eu precisaria para memoizar tudo? É um inteiro para cada índice... ou seja, precisaria de 10<sup>9</sup> inteiros para tentar memoizar todas as entradas para `fib(n)`. Mas a questão é que não estamos calculando `fib(n)`, mas `fib(fib(n))`, o que exigiria um tanto mais de memória... de toda sorte, 1 bilhão de inteiros já exigiria (para um intiero de 32 bits) 4GB de RAM **só para o vetor de memoização**. Bem, eu não sei quanto o URI disponibiliza, mas com certeza é menos do que isso...

Então, essa alternativa memoizada _também_ está fora de cogitação.

E calcular de forma linear? Como você mesmo, @rafael marques, sugeriu? Bem, é feito de forma linear. Na pior das hipóteses, então, a entrada seria 1 bilhão e, para calcular o Fibonacci só disso, seriam necessárias bilhões de operações. Então, essa alternativa **também** não é viável...

É necessário uma abordagem mais rápida do que [`o(n)`](https://pt.stackoverflow.com/q/236960/64969). Talvez uma abordagem `o(log n)` poderia ser aceita, mas acho que uma abordagem `o(1)` é melhor.

Peguemos a fórmula novamente:

[![fórmula de Fibonacci][1]][1]

Preste atenção no termo do lado direito: `(1 -  φ)^n/sqrt(5)`. Se você for calcular, verá que o valor absoluto desse número é sempre menor que 0.5. Então, podemos obter o valor de `fib(n)` através da seguinte fórmula:

[![nova leitura da fórmula de Fibonacci][3]][3]

> [Fonte](https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding)

Assim sendo, consigo calcular `fib(n)`. Mas... será mesmo? Para tal, precisamos garantir que o número calculado caiba dentro do espaço de memória reservado para tal. Uma variável do tipo `double` só tem 53 bits de mantissa. Isso não é suficiente nem para armazenar a entrada inteira, que pode chegar a 1 bilhão, portanto precisara de uns 62 dígitos para ser armazenado. Então, o tipo `double` não é adequado. E `long double`? Bem, ele é garantidamente não menor que um `double` ([fonte](https://en.wikipedia.org/wiki/C_data_types)), mas em nenhum momento eu vi definição garantida dele. Talvez seja um [ponto flutuante extendido do x86](https://en.wikipedia.org/wiki/Extended_precision#x86_extended_precision_format), que usa 64 bits de mantissa ([veja mais](https://pt.stackoverflow.com/q/219211/64969)). Ou seja, nada feito ainda.

Se pelo menos fosse possível usar esse `mod m` em algum lugar...

[![loding...][4]][4]

Mas, existe o período de Pisano!!

[![loaded!!][5]][5]

O [período de Pisano](https://en.wikipedia.org/wiki/Pisano_period) é o tamanho do intervalo em que os números da sequência de Fibonacci começam a se repetir, `mod m`. O interessante desse período é que `fib(n) % m = fib(n % π(m)) % m`, sendo `π(m)` é o período de Pisano para o módulo `m`. E o interessante é que `π(m) <= 6*m`. Daí, calcular `fib(n) % m` não é mais dependente de `n`, mas é `o(π(m))`, e como temos que `π(m) = o(m)`, então o cálculo de uma sequência de Fibonacci módulo `m` é `o(m)`. E isso está dentro do nosso aceitável.

Então, com isso, revisando aqui o nosso objeto de cálculo:

[![fib(fib(n))mod m][6]][6]

Que portanto é igual a:

[![fib(fib(n) % pi(m)) % m][7]][7]

Que portanto é igual a:

[![fib(fib(n % pi(pi(m))) % pi(m)) % m][8]][8]

Muito bem, com isso, o cálculo iterativo de `fib` é bom o suficiente. Voltemos a como fazer esse cálculo em breve, pois antes precisamos definir uma outra ponta solta na solução... o valor de `π(m)`.

Diversas outras pessoas já se depararam com a necessidade de fazer o cálculo da função de Fibonacci para números grandes. Como [esse rapaz do artigo](https://medium.com/competitive/huge-fibonacci-number-modulo-m-6b4926a5c836)). E, sim, ele foi uma das referências que encontrei quando buscava sobre o cálculo de `π(m)`. Em resumo, é algo muito próximo de calcular o valor de `fib(n)`, mas a ideia é que ao obter o valor 0 e, em seguida, obter o valor 1, entrou-se em laço. O número `n ==> fib(n)%m == 0, fib(n + 1)%m == 1`  é o tamanho do período de Pisano; ou seja, `n <==> π(m)`.

Então, para calcular o `π(m)` é necessário calcular a função de Fibonacci. Para isso, vou usar a adaptação do cálculo iterativo que você fez:

    def pisano(m):
    	if m == 1:
    		return 1
    		
    	"""
    	toda sequência tem tamanho par, então posso começar de n = 2 e terminar quando
    	obter:
    	
    	f_n_minus_1 == 0
    	f_n == 1
    	"""
    	
    	f_n_minus_1 = 1
    	f_n = 1
    	n = 2
    	
    	while not(f_n_minus_1 == 0 and f_n == 1):
    		f_n_plus_1 = (f_n + f_n_minus_1) % m
    		f_n_minus_1 = f_n
    		f_n = f_n_plus_1
    		n += 1
    	return n - 1

[Veja funcionando no ideone](https://ideone.com/1tViOS). Note que, aqui, minha validação é para `fib(n - 1) % m == 0, fib(n) % m == 1`, então aqui `n` é `π(m) + 1` no final do laço; por isso que o retorno é `n - 1`, mas claro que isso poderia ser alterado (mas daí os nomes das variável `fib_n`, `fib_n_plus_1` e `fib_n_minus_1` não fariam sentido, teria de renomear).

Então, como proceder com a conta? Poderíamos usar memoização para evitar calcular duas vezes o mesmo valor de `π(x)`. Para tal, o vetor de memória deveria ter o tamanho de mais ou menos 6 milhões de inteiros (limite superior para `π(m), m <= 1000000`, para realizar o cálculo de `π(π(m))`). Vou deixar essa parte com você. E o cálculo da sequência de Fibonacci módulo m, então? Como ficaria?

Se reparou bem, é necessário passar sempre por todos os valores da sequência de Fibonacci menores do que o período para achar o período. Talvez fosse o caso de armazenar esses valores intermediários em um vetor e acessá-los em `o(1)`. Vou deixar para você pensar em como resolver.

Para resolver a questão, precisamos escrever `fib(fib(n))%m`, que batizo de `fib_fib_mod`. Ela seria assim:

    def fib_fib_mod(n, m):
      return fib_mod(fib_mod(n, pisano(m)), m)

Já `fib_mod`:

    def fib_mod(n, m):
      n = n % pisano(m)
      if n == 0:
        return 0
      f_x_minus_1 = 0
      f_x = 1
      x = 1
      while x < n:
        f_x_plus_1 = (f_x + f_x_minus_1) % m
        f_x_minus_1 = f_x
        f_x = f_x_plus_1
        x += 1
      return f_x

Deixei o código em Python para que você precise adaptá-lo para C. E, na adpatação, fazer as mudanças necessárias para tentar otimizar o cálculo, como memoizar os diversos cálculos no meio do caminho para evitar repetir cálculos prévios. [Veja funcionando para algumas entradas no ideone](https://ideone.com/LB44B9).

# Conclusão

- esse problema é muito mais de matemática do que programação, não seria possível pensar em resolução para ele sem conhecer as sequências de Pisano
- sempre leia os limites da questão; se a questão disse que o máximo para uma variável é 1 bilhão, então os criadores da prova pensaram em um caso de entrada para 1 bilhão
- mesmo que você tenha uma solução `o(n)`, ele vai ser inutilmente lenta caso o valor de `n` seja muito grande, como 1 bilhão
- teste para casos além dos casos em que o criador da prova mostrou  
  aqueles ali são só meros exemplos para você se basear, ter um norte, principalmente no **_formato_** de entrada e saída de dados; muito mais do que outra coisa, as pessoas que criam essas provas gostam de mostrar de maneira a não ter dúvidas qual o formato de entrada e o formato esperado de saída
- as vezes, a melhor otimização em um programa é sair o mais longe possível da programação e usar fórmulas mágicas, como a de cálculo do período de Pisano

  [1]: https://i.sstatic.net/c06FR.png
  [2]: https://i.sstatic.net/zGrlG.png
  [3]: https://i.sstatic.net/dH4qR.png
  [4]: https://i.sstatic.net/esmmr.gif
  [5]: https://i.sstatic.net/W4Qy9.gif
  [6]: https://i.sstatic.net/pCrlI.png
  [7]: https://i.sstatic.net/ACwMK.png
  [8]: https://i.sstatic.net/rRSWl.png