¿Cuál es el algoritmo eficiente para encontrar la suma de los dígitos del factorial de un número (el número puede ser hasta 500), es decir, para num = 5, ans = 3 (como 5! = 120)?

un hecho sobre esto es después de 5 la suma de dígitos factoriales de cada número es = 9 (si lo expresamos en un solo dígito)
6! = 720 = 9
7! = 5040 = 9
8! = 40320 = 9
9! = 362880 = 3 + 6 + 2 + 8 + 8 + 0 = 27 = 2 + 7 = 9
similar….
10! = 3628800 = 9
11! = 39916800 = 9
12! = 479001600 = 9
13! = 6227020800 = 9
14! = 87178291200 = 9
¡15! = 1307674368000 = 9
¡dieciséis! = 20922789888000 = 9
17! = 355687428096000 = 9
18! = 6402373705728000 = 9
19! = 121645100408832000 = 9
20! = 2432902008176640000 = 9

#include
int main () {
unsigned int dig [10000], first = 0, last = 0, carry, n, x, sum = 0;
dig [0] = 1;
para (n = 2; n <= 9999; n ++) {
llevar = 0;
para (x = primero; x <= último; x ++) {
carry = dig [x] * n + carry;
dig [x] = carry% 100000;
if (x == first &&! (carry% 100000)) first ++;
llevar / = 100000; }
if (carry) dig [++ last] = carry; }
para (x = primero; x <= último; x ++)
sum + = dig [x]% 10 + (dig [x] / 10)% 10 + (dig [x] / 100)% 10 + (dig [x] / 1000)% 10
+ (dig [x] / 10000)% 10;
printf (“Suma:% d \ n”, suma);
}

Suma de dígitos de un factorial

Una forma de hacerlo es calculando realmente el factorial.
Obviamente, usar estructuras de datos primitivas como int, long será una mala idea.
Entonces podemos usar una matriz para almacenar el valor factorial y usar un algoritmo de multiplicación simple
[Puedes ver un buen tutorial escrito sobre esto en codechef
Tutorial para pequeños factoriales]

  import java.io. *;
 import java.util. *;

 clase pública FactorialSum {
 public static void main (String args []) lanza Exception
 {
 BufferedReader br = new BufferedReader (nuevo InputStreamReader (System.in));
 int i = 0, j = 0, k = 0, n = 0, factorial [] = new int [200000], sum = 0, carry = 0, temp;
 n = Integer.parseInt (br.readLine ()); // n es el número cuyo factorial se requiere;
 tratar{
 factorial [0] = 1; k = 1;
 para (i = 2; i <= n; i ++)
 {carry = 0;
 para (j = 0; j  0)
 {
 factorial [k] = llevar% 10;
 llevar = llevar / 10;
 k ++;
 }
 }

 para (i = 0; i 
  Lo he probado hasta 25000 y funciona bien. 
  Mientras estaba haciendo una verificación cruzada de mis respuestas para diferentes valores en Wolfram Alpha. 
  Encontré que las respuestas estaban representadas de manera interesante.  Además de suma 
  El recuento de dígitos individuales (0 a 9) en n!  también se proporcionó (ver suma de dígitos en 25000!). 
  Estoy pensando en el recuento de dígitos individuales en n!  se calculó? Obviamente podemos hacerlo usando el código dado anteriormente.  Pero si hay algún otro enfoque mejor, ¡calculará la suma de dígitos en n!  de una manera mucho mejor 
  (Publicó una nueva pregunta para este Algoritmo: ¿Es posible calcular el recuento de dígitos individuales en n! Sin calcular n !?) 
    

  "" "Programa Python" ""
 def sod (n):
     # sod - suma de dígitos
     s = str (n) #convertir a cadena
     total = 0
     para i en rango (0,10):
         total + = s.count (str (i)) * i
     retorno total

 tabla = [1,1]
 hecho definido (n):
     si n 
  por 500 es 4599 🙂 

    

Es esencialmente el resto obtenido cuando un número se divide por 9, excepto que en el caso de que el resto sea 0, la suma será 9.

Ahora, cada factorial a partir de 6! siempre es divisible por 9 y, por lo tanto, todos sumarán 9. ¡Para factoriales menores a 6 !, creo que no es un gran problema encontrar el resto cuando se divide entre 9