Skip to main content
adicionou 12 caracteres ao conteúdo
Fonte Link
Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158

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 maior que 1 deixará ele mais próximo de zero.

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 109 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 intierointeiro 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...

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.

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 109 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...

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 maior que 1 deixará ele mais próximo de zero.

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 109 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 inteiro 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...

Commonmark migration
Fonte Link

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

###Entrada

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 ≤ 109, 2 ≤ M ≤ 106).

[...] 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 ≤ 109, 2 ≤ M ≤ 106).

[...] 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 ≤ 109, 2 ≤ M ≤ 106).

Pequenos ajustes de digitação
Fonte Link
Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158

loding...loading...

O período de Pisano é 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.

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). 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).

loding...

O período de Pisano é 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.

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). 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).

loading...

O período de Pisano é 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.

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. 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).

removeu 2 caracteres do conteúdo
Fonte Link
Woss
  • 77,2mil
  • 15
  • 123
  • 221
Carregando
Fonte Link
Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158
Carregando