Cod sursa(job #221624)

Utilizator mihai.gheteMihai Ghete mihai.ghete Data 17 noiembrie 2008 01:22:53
Problema Factorial Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdlib.h>
#include <stdio.h>

int main(){
  long long n;
  long long p;

  long long p5;
  long long i;

  FILE* f = fopen("fact.in", "r");
  FILE* o = fopen("fact.out", "w");

  fscanf(f, "%lld",&p);

  /* assert lower bound is p*4 
     TODO: proof
   */

  if (p == 0) {
    fprintf(o, "%d\n", 1);
    return 0;
  }

  n = p*4;
  n -= n%5;

  //printf("lower bound: %lld\n", n);

  /* calculate the index */

  p5 = 0;
  i = n;

  while (i>=5) {
    p5 += (i/=5);
  }

  //printf("index of lower bound: %lld\n", p5);

  i = n;
  while (p5 < p && (i+=5)) {
    long long x = i/5;
    p5++;
    while (x && !(x % 5)) {
      x /= 5;
      p5++;
    }
  }

  if (p5 > p)
    fprintf(o, "-1\n");
  else
    fprintf(o, "%lld\n", i);

  return 0;
}