Suma de dígitos de un factorial.
No es una pregunta de tarea. Solo pensé que alguien podría saber una solución real a este problema.
Yo estaba en un concurso de programación en 2004, y había un problema:
Dado n, encuentra la suma de dígitos de n !. n puede ser de 0 a 10000. Tiempo límite: 1 segundo. Creo que había hasta 100 números para cada conjunto de prueba.
Mi solución fue bastante rápida, pero no lo suficientemente rápida, así que la dejé correr por un tiempo. Construyó una matriz de valores precalculados que podría usar en mi código. Fue un hack, pero funcionó.
Pero hubo un tipo, que resolvió este problema con aproximadamente 10 líneas de código y daría una respuesta en ningún momento. Creo que fue una especie de programación dinámica, o algo de la teoría de los números. Teníamos 16 en ese momento, así que no debería ser una "ciencia de cohetes".
¿Alguien sabe qué tipo de algoritmo podría usar?
EDITAR: Lo siento si no aclaro la pregunta Como dijo mquander, debería haber una solución inteligente, sin errores, con solo el código Pascal, un par de bucles, O (n2) o algo así. 1 segundo ya no es una restricción.
encontréaquí eso si n> 5, entonces 9 divide la suma de dígitos de un factorial. También podemos encontrar cuántos ceros hay al final del número. ¿Podemos usar eso?
Ok, otro problema del concurso de programación de Rusia. Dado 1 <= N <= 2 000 000 000, salida N! mod (n + 1). ¿Está eso relacionado de alguna manera?