Cod sursa(job #1542846)

Utilizator TincaMateiTinca Matei TincaMatei Data 5 decembrie 2015 18:41:23
Problema Factorial Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#define MAX_N 400000015
#define NU_EXISTA -1

int min( int a , int b ) {
  if( a < b )
    return a;
  else
    return b;
}

//formula lui Legendre pt un nr n si un nr prim p
int legendrePrim( int p , int n ) {
  int s;
  s = 0;
  while( n > 0 ) {
    s = s + n / p;
    n = n / p;
  }
  return s;
}

//formula lui Legendre pt un nr n si 10
int legendre10( int n ) {
  return legendrePrim( 5 , n );
}

int main() {
  int p , min , max , mid , n;
  FILE *fin = fopen( "factorial.in" , "r" );
  fscanf( fin , "%d" , &p );
  min = 0;
  //MAX_N este cel mai mic n pt care p este maxim,adica 10^8
  max = MAX_N;
  fclose( fin );

  //cautam binar valoarea lui n
  while( max - min > 1 ) {
    mid = ( min + max ) / 2;
    if( legendre10( mid ) >= p )
      max = mid;
    else
      min = mid;
  }

  //verificam daca valoarea gasita are p cifre de 0 la sfarsit
  if( legendre10( max ) == p )
    n = max;
  else
    n = NU_EXISTA;

  FILE *fout = fopen( "factorial.out" , "w" );
  fprintf( fout , "%d" , n );
  fclose( fout );
  return 0;
}