Ayuda de pregunta de práctica de Codechef necesaria - encuentre ceros al final en un factorial

Question

He estado trabajando en esto durante 24 horas, tratando de optimizarlo. La pregunta es cómo encontrar el número de ceros finales en factorial de un número en el rango de 10000000 y 10 millones de casos de prueba en aproximadamente 8 segundos.

El código es el siguiente:

#include<iostream> 

using namespace std; 

int count5(int a){ 
    int b=0; 
    for(int i=a;i>0;i=i/5){ 
     if(i%15625==0){ 
      b=b+6; 
      i=i/15625; 
     } 
     if(i%3125==0){ 
      b=b+5; 
      i=i/3125; 
     } 
     if(i%625==0){ 
      b=b+4; 
      i=i/625; 
     } 
     if(i%125==0){ 
      b=b+3; 
      i=i/125; 
     } 
     if(i%25==0){ 
      b=b+2; 
      i=i/25; 
     } 
     if(i%5==0){ 
      b++; 
     } 
     else 
      break; 

    } 
    return b; 
} 
int main(){ 
    int l; 
    int n=0; 
    cin>>l; //no of test cases taken as input 
    int *T = new int[l]; 

    for(int i=0;i<l;i++) 
     cin>>T[i]; //nos taken as input for the same no of test cases 


    for(int i=0;i<l;i++){ 
     n=0; 
     for(int j=5;j<=T[i];j=j+5){ 
      n+=count5(j); //no of trailing zeroes calculted 
     } 
     cout<<n<<endl; //no for each trialing zero printed 
    } 

    delete []T; 


} 

favor me ayude por lo que sugiere un nuevo enfoque, o sugerir algunas modificaciones a éste.

Answer 1

Utilice el siguiente teorema:

Si p es un número primo, entonces el mayor potencia de p que divide n! (n factorial) es [n/p] + [n/p^2] + [n/p^3] + ... + [n/p^k], donde k es la mayor potencia de p < = n, y [x] es la parte integral de x.

Referencia: http://planetmath.org/encyclopedia/PrimePowerDividingAFactorial.html

Answer 2

La solución óptima se ejecuta en O(log N) tiempo, donde N es el número al que desea encontrar los ceros para. Utilice esta fórmula:

Zeroes(N!) = N/5 + N/25 + N/125 + ... + N/5^k, hasta que una división se convierta en 0. Puede leer más en wikipedia.

Así, por ejemplo, en C esto sería:

int Zeroes(int N) 
{ 
    int ret = 0; 
    while (N) 
    { 
     ret += N/5; 
     N /= 5; 
    } 
    return ret; 
} 

Esto ejecutará en 8 segundos en un ordenador lo suficientemente rápido. Probablemente puedas acelerarlo usando tablas de búsqueda, aunque no estoy seguro de cuánta memoria tienes disponible.

Aquí hay otra sugerencia: ¡no almacene los números, no los necesita! Calcule el número de ceros para cada número cuando lo lea.

Si esto es para un juez en línea, en mi experiencia los jueces en línea exageran los límites de tiempo en los problemas, por lo que tendrá que recurrir a feos hacks incluso si tiene el algoritmo correcto. Uno de esos feos hack es no usar funciones como cin y scanf, sino usar fread para leer un montón de datos a la vez en una matriz char, luego analizar esos datos (NO use sscanf o stringstreams) y obtener los números fuera de el. Feo, pero mucho más rápido por lo general.

Answer 3

Usted ya sabe claramente el algoritmo correcto. El cuello de botella en su código es el uso de cin/cout. Cuando se trata de una entrada muy grande, cin es extremadamente lento en comparación con scanf.

scanf también es más lento que los métodos directos de lectura de entrada como fread, pero usar scanf es suficiente para casi todos los problemas en los jueces en línea.

Esto se detalla en el Codechef FAQ, que es probablemente vale la pena leer primero;)

Answer 4

Esta pregunta es de codechef.

http://www.codechef.com/problems/FCTRL

¿Qué hay de esta solución:

#include <stdio.h> 

int a[] = {5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625}; 

int main() 
{ 
    int i, j, l, n, ret = 0, z; 
    scanf("%d", &z); 
    for(i = 0; i < z; i++) 
    { 
     ret = 0; 
     scanf("%d", &n); 
     for(j = 0; j < 12; j++) 
     { 
      l = n/a[j]; 
      if(l <= 0) 
       break; 
      ret += l; 
     } 
     printf("%d\n", ret); 
    } 
    return 0; 
} 

optimizaciones ???

Answer 5

sabe que esto es más de 2 años de edad, pero aquí está mi código para referencia futura:

#include <cmath> 
#include <cstdio> 

inline int read() 
{ 
    char temp; 
    int x=0; 
    temp=getchar_unlocked(); 
    while(temp<48)temp=getchar_unlocked(); 
    x+=(temp-'0'); 
    temp=getchar_unlocked(); 
    while(temp>=48) 
    { 
     x=x*10; 
     x+=(temp-'0'); 
     temp=getchar_unlocked(); 
    } 
    return x; 
} 
int main() 
{ 
    int T,x,z; 
    int pows[]={5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125,244140625}; 
    T=read(); 
    for(int i=0;i<T;i++) 
    { 
     x=read(); 
     z=0; 
     for(int j=0;j<12 && pows[j]<=x;j++) 
      z+=x/pows[j]; 
     printf("%d\n",z); 
    } 
    return 0; 
} 

corrió en los 0.13s

Answer 6

Aquí está mi solución aceptada. Su puntaje es 1.51s, 2.6M. No es el mejor, pero tal vez pueda ayudarte.

#include <iostream> 
using namespace std; 

void calculateTrailingZerosOfFactoriel(int testNumber) 
{ 

    int numberOfZeros = 0; 
    while (true) 
    { 

     testNumber = testNumber/5; 
     if (testNumber > 0) 
      numberOfZeros += testNumber; 
     else 
      break; 
    } 
    cout << numberOfZeros << endl; 
} 

int main() 
{ 

    //cout << "Enter number of tests: " << endl; 
    int t; 
    cin >> t; 

    for (int i = 0; i < t; i++) 
    { 
     int testNumber; 
     cin >> testNumber; 
     calculateTrailingZerosOfFactoriel(testNumber); 
    } 
    return 0; 
} 

Answer 7

#include <cstdio> 

int main(void) { 
    long long int t, n, s, i, j; 
    scanf("%lld", &t); 
    while (t--) { 
     i=1; s=0; j=5; 
     scanf("%lld", &n); 
     while (i != 0) { 
      i = n/j; 
      s = s + i * (2*j + (i-1) * j)/2; 
      j = j * 5; 
     } 
     printf("%lld\n", s); 
    } 
    return 0; 
}