Pagini recente » Cod sursa (job #530757) | Cod sursa (job #2640303) | Cod sursa (job #76312) | Cod sursa (job #1408922) | Cod sursa (job #697299)
Cod sursa(job #697299)
#include <stdio.h>
#define MAX_N 999999999
/* This program determines the first n such n! has exactly p trailing zeros.
* It computes it, using binary search and a mathematical formula for determining the number of trailing 0's of n!.
*/
/* function that returns the number of zeros of n!, with n as argument */
int noZeros(int n){
int zeros = 0, fives = 5, div;
while((div = n / fives) != 0){
zeros += div;
fives *= 5;
}
return zeros;
}
/* function that determines the minimum n for which n! has p trailing zeros, using binary search algorithm */
int determineFact(int p){
int min = 0, max = MAX_N, med, zeros, val = -1;
while(min <= max){
/* invariant: if a[i]==val for any i, then lower <= i <= upper */
med = min + (max - min)/2;
zeros= noZeros(med);
if(zeros == p){
return med - med % 5; // return the smallest possible n!
}
if(zeros > p){
max = med - 1;
}
else {
min = med + 1;
}
}
return val;
}
int main(){
freopen("fact.in", "r", stdin);
freopen("fact.out", "w", stdout);
int p, n;
scanf("%d", &p); // read the number of zeros
fclose(stdin);
if(p == 0){
putchar('1');
return 0;
}
n = determineFact(p);
printf("%d",n);
fclose(stdout);
return 0;
}