Cod sursa(job #1886216)

Utilizator Matei_2001Matei Popa Matei_2001 Data 20 februarie 2017 19:07:51
Problema Factorial Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
using namespace std;
ifstream f("fact.in");
ofstream g("fact.out");

#define N 200000 

int numara_zerouri(int n);  // numara zerourile de la sfarsitul numarului factorial(n)
int numara_2(int n);        // numara cati de 2 se afla in descompunerea in factori primi a lui n
int numara_5(int n);

int zerouri_pentru_nr_deja_incercate[N] = {0};

int main(void)
{
  int p, n = 1, zerouri = 0;
  
  f >> p;
    
  for (n = 5;; n++)
  {
    zerouri = numara_zerouri(n);	
	
	if (zerouri == p)
      break;
    else if (zerouri > p)
	{
      n = -1;
      break;	  
    } 
  } 	  

  g << n;
  
  return 0;
}


int numara_zerouri(int n)
{
  int i, zerouri = 0, cati_de_2 = 0, cati_de_5 = 0;                                                 

  if (zerouri_pentru_nr_deja_incercate[n])
    return zerouri_pentru_nr_deja_incercate[n];	  
  
  for (i = 2; i <= n; i++)
  {
    if (!(i % 2))
	  cati_de_2 += numara_2(i);

    if (!(i % 5))
      cati_de_5 += numara_5(i);		
  }

  while (cati_de_5 && cati_de_2)
  {
	++zerouri;
    --cati_de_2;
    --cati_de_5;	
  }

  zerouri_pentru_nr_deja_incercate[n] = zerouri;
  
  return zerouri;  
}

int numara_2(int n)
{
  int numar_de_2 = 0;

  while (!(n % 2))
  {
	++numar_de_2;
    n /= 2;	
  }

  return numar_de_2;  
} 


int numara_5(int n)
{
  int numar_de_5 = 0;

  while (!(n % 5))
  {
	++numar_de_5;
    n /= 5;	
  }

  return numar_de_5;  
}