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