Pagini recente » Rating Florin Diaconescu (Houstain) | Monitorul de evaluare | Cod sursa (job #545908) | Cod sursa (job #1659189) | Cod sursa (job #2659966)
#include <stdio.h>
// use a type that can hold numbers between 0 and 10^8
typedef unsigned long long ulong;
// count trailing zeros in n's factorial
// using this formula
// trailing0s = floor(n/5) + floor(n/25) + floor(n/125) + ...
// we'll stop when floor(n / pow(5, x)) == 0
int countTrailingZeros(ulong n) {
int count = 0;
for (ulong i = 5; n / i >= 1; i *= 5) {
count += n / i;
}
return count;
}
// we can observe that for every number n
// 5 * n contains at least n trailing zeros
// search to numbers from 0 to 5 * n
// using binary search
ulong solve(int n) {
if (n < 0)
return 0;
// base cases
if (n == 0)
return 1;
if (n == 1)
return 5;
ulong low = 2;
ulong high = 5 * (ulong)n;
// iterative implementation
// to reduce memory usage
while (low < high) {
ulong mid = (low + high) / 2;
if (countTrailingZeros(mid) >= n)
high = mid;
else
low = mid ;
}
return low;
}
int main() {
FILE* in, *out;
in = fopen("fact.in", "r");
if (!in) {
fprintf(stderr, "Error while opening fact.in, check if file exists!\n");
return 0;
}
out = fopen("fact.out", "w");
if (!out) {
fprintf(stderr, "Error while opening fact.out\n");
fclose(in);
return 0;
}
int n;
fscanf(in, "%d", &n);
fprintf(out, "%llu\n", solve(n));
fclose(in);
fclose(out);
return 0;
}