Euler 160: Encuentre los 5 dígitos no triviales del factorial

¡Dado un número, encuentre los 5 dígitos antes del 0,99 posterior! = 362880 tan f (9) = 36288 10! = 3628800 entonces f (10) = 36288 20! = 2432902008176640000 tan f (20) = 17664 Calcula f (1.000.000.000.000)Euler 160: Encuentre los 5 dígitos no triviales del factorial

Para esto he calculado la f(10^6)f(10^12) = (f(10^6))^(10^6) y luego para calcular la f(n) ... estoy computación en el factorial mediante la eliminación de cualquier 5 y que corresponde 2 para que se eliminen todos los ceros .
Pero recibo una respuesta incorrecta.
¿Hay algún problema en el enfoque o algún error tonto?

Código

para referencia

long long po(long long n, long long m, long long mod) { 
    if (m == 0) return 1; 
    if (m == 1) return n % mod; 
    long long r = po(n, m/2, mod) % mod; 
    if (m % 2 == 0) return (r * r) % mod; 
    return (((r * r) % mod) * n) % mod; 
} 

void foo() { 
    unsigned long long i, res = 1, m = 1000000 , c = 0, j, res1 = 1, mod; 
    mod = ceil(pow(10, 9)); 
    cout << mod << endl; 
    long long a = 0, a2 = 0, a5 = 0; 
    for (i = 1 ; i <= m; i++) { 
     j = i; 
     while (j % 10 == 0) 
      j /= 10; 
     while (j % 2 == 0) { 
      j /= 2; 
      a2++; 
     } 
     while (j % 5 == 0) { 
      j /= 5; 
      a5++; 
     } 
     res = (res * j) % mod; 
    } 

    a = a2 - a5; 

    for (i = 1; i <= a; i++) 
     res = (res * 2) % mod; 
    for (i = 1; i <= 1000000; i++) { 
     res1 = (res1 * res) % mod; 
    } 
    cout << res1 << endl; 
}

Fuente

2012-02-17 titan

¿Puedes publicar tu código? – 0605002

también, no es algo del proyecto euler que deba resolver usted mismo en lugar de pedir ayuda ... solo dice que si deja que alguien más lo resuelva, no solo obtendrá nada de eso sino que también la respuesta estará ahora en TAN para que todos lo vean – hackartist

Su igualdad f(10^12) = (f(10^6))^(10^6) está mal. f() se basa en factoriales, no poderes.

Fuente

2012-02-17 18:57:55

Mi hipótesis: ¡hemos calculado los últimos 5 dígitos de (10^6)! ¡ahora todos los demás dígitos> 10^6 tendrán los mismos 5 dígitos finales con los cuales hemos calculado el (10^6)! So f (2 * (10^6)) = f (10^6)! * f (10^6) De manera similar f (n * 10^6) = (f (10^6))^n – titan

@titan: pero los ceros finales en los números significan que no se puede tratar el todo problema módulo 1000000 así. Por ejemplo, 123000 en su primer millón aportará dígitos diferentes al 5 que 1123000, por lo que no son equivalentes. –

sus suposiciones son erróneas:

f (10^12) no es el mismo que f (10^6)^(10^6).
con el fin de obtener el orden bajo no 0 dígitos del factorial, no es suficiente para eliminar todos los múltiplos de 10, 2 y 5 de los multiplicandos. Es una buena idea eliminar los múltiplos de 10, para 5 y 2, debe eliminar el factor 2 o 5 solo si el otro multiplicando es un múltiplo de 5 y 2 respectivamente.

Debe simplificar el código y calcular módulo alguna potencia de 10, pero 10^9 parece demasiado alto como 10^9 * 10^12 se desbordará de 64 bits tipo unsigned long long.

Fuente

2017-02-13 20:29:24 chqrlie

Euler 160: Encuentre los 5 dígitos no triviales del factorial

Respuesta

Cuestiones relacionadas