Cod sursa(job #22106)

Utilizator costinbCostin Boldisor costinb Data 25 februarie 2007 17:29:15
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <stdio.h>
#include <math.h>

/* Intoarce floor de log5(n) */
inline int log5(long long n){
	long long crt = 5;

	int rez = 0;
	while(crt <= n){
		crt *= 5;
		++rez;
	}

	return rez;
}

/* Calc numarul de zerouri ale lui n!
Mathworld: Z = sum(k=1:log5(n))(n/5^k)
*/
int trailingz(long long n){
	int kmax = log5(n);
	int z=0;

	for(int k = 1 ; k <= kmax ; ++k){
		z += (int)((long double)n / pow((long double)5,(long double)k));
	}

	return z;
}

/* Cauta numarul nr in vectorul v de lungime len 
@returns: -1 daca nu a gasit, poz daca la gasit 
*/
int search(int nr, int* v, int len){
	int shift, k;

	for(shift = 1 ; shift < len ; shift <<= 1);

	for(k=0 ; shift > 0 ; shift >>= 1){
		
		if((k | shift) < len && v[k | shift] <= nr)
			k |= shift;
		
	}

	if(v[k] != nr)
		return -1;
	else
		return k;
}

/* Cel mai mic numar natural care are P zerouri la sfarsit */
long long cmmFact(int p){
	long long shift, k;

	for(shift = 1 ; trailingz(shift) < p ; shift <<= 1);

	for(k=0 ; shift > 0 ; shift >>= 1){

		if(trailingz(k | shift) <= p)
			k |= shift;
	}

	if(trailingz(k) != p)
		return -1;
	else{
		int lastgood = k;
		do{
			--k;
			if(trailingz(k) == p)
				lastgood = k;
			else 
				break;
		}while(1);
		return lastgood;
	}
}

int main(){
	freopen("fact.in","r",stdin);	
	freopen("fact.out","w",stdout);

	int P;
	scanf("%d",&P);
	if(P == 0)
		printf("1\n");
	else
		if(P == 1)
			printf("5\n");
		else
			printf("%d\n",cmmFact(P));
	return 0;
}