Pagini recente » Borderou de evaluare (job #583876) | Cod sursa (job #584227)
Cod sursa(job #584227)
/**
* 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;
}