Cod sursa(job #584227)

Utilizator caen1c a e n caen1 Data 24 aprilie 2011 18:31:38
Problema Factorial Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.14 kb
/**
 * user: caen1
 * file: infoarena/fact.c
 * date: 24 apr 2011
**/
#include <stdio.h>

#define IN "fact.in"
#define OUT "fact.out"
#define NF -1
#define N 1000000000LL

static long long cautbin(int, long long, long);
static long cif(long long);
static long exp1(long, long);

int main(void) {

    long p;

    (void) freopen(IN, "r", stdin);
    (void) freopen(OUT, "w", stdout);

    (void) scanf("%ld", &p);

    if(!p) printf("1\n");
    else printf("%lld\n", cautbin(0, N, p));

    return 0;
}

long long cautbin(int lo, long long hi, long p) {

    long long mid;
    long ncif;

    do {

        mid = lo + (hi - lo) / 2;
        ncif = cif(mid);

        if(ncif > p) hi = mid - 1;
        else if(ncif < p) lo = mid + 1;
    } while(ncif != p && lo < hi);

    if(ncif != p) return NF;
    else while(cif(mid - 1) == ncif) --mid;

    return mid;
}

long cif(long long n) {

    long rez = 0, k = 0, i;

    while(exp1(5, k++) <= n) ;

    for(i = 1; i < k; ++i) rez += n / exp1(5, i);

    return rez;
}

long exp1(long n, long e) {

    long rez;

    if(!e) return 1;

    rez = exp1(n, e >> 1);
    rez *= rez;
    if(e & 1) rez *= n;

    return rez;
}