Soma dos dígitos de um fatorial
Não é uma questão de lição de casa. Eu apenas pensei que alguém poderia conhecer uma solução real para esse problema.
Eu estava em um concurso de programação em 2004, e havia esse problema:
Dado n, encontre a soma dos dígitos de n !. n pode ser de 0 a 10000. Limite de tempo: 1 segundo. Eu acho que havia até 100 números para cada conjunto de testes.
Minha solução foi bem rápida, mas não rápida o suficiente, então deixei ela rodar por algum tempo. Ele criou uma matriz de valores pré-calculados que eu poderia usar no meu código. Foi um hack, mas funcionou.
Mas havia um cara, que resolveu esse problema com cerca de 10 linhas de código e daria uma resposta em pouco tempo. Eu acredito que foi algum tipo de programação dinâmica, ou algo da teoria dos números. Nós tínhamos 16 anos naquela época, então não deveria ser uma "ciência de foguetes".
Alguém sabe que tipo de algoritmo ele poderia usar?
EDITAR: Me desculpe se eu não fiz a pergunta clara. Como mquander disse, deve haver uma solução inteligente, sem bugnum, com apenas o código Pascal, par de loops, O (n2) ou algo assim. 1 segundo não é mais uma restrição.
eu encontreiAqui que se n> 5, então 9 divide soma de dígitos de um fatorial. Nós também podemos encontrar quantos zeros existem no final do número. Podemos usar isso?
Ok, outro problema de concurso de programação da Rússia. Dado 1 <= N <= 2 000 000 000, N de saída! mod (N + 1). Isso está de alguma forma relacionado?