Cod sursa(job #245847)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 19 ianuarie 2009 00:31:51
Problema Factorial Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#define infile "fact.in"
#define outfile "fact.out"

//returneaza numarul de zerouri al lui n!
long long f(long long n)
	{
	long long z=0,k=5;
	while(k<=n)
		{
		z+=n/k; //numarul de numere divizibile cu 5
		k*=5; //trebuie sa luam 5^i, cat timp 5^i<=n
		}
	return z; //returnam numarul de zerouri
	}

//cautam binar solutia
long long cbin(long long z)
	{
	long long p=z,q=1<<31,m,x,r=-1;
	while(p<=q)
		{
		m=(p+q)/2; //cautam mijlocul
		x=f(m); //luam numarul de zerouri
		if(x==z && (m<r || r==-1)) r=m; //avem numarul de zerouri exact
		//nu oprim cautarea....poate exista solutie mai mica
		if(x>=z) q=m-1; //aem prea multe zerouri, restrangem cautarea in partea stanga
		else p=m+1; //avem prea putine zerouri, restrangem cautarea in partea dreapta
		}
	return r; //returnam rezultatul
	}

int main()
{
long long z; //numarul de zerouri
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

scanf("%lld",&z); //citim numarul de zerouri
printf("%lld",cbin(z));

fclose(stdin);
fclose(stdout);
return 0;
}