Cod sursa(job #53359)

Utilizator peanutzAndrei Homorodean peanutz Data 21 aprilie 2007 21:06:54
Problema Factorial Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <stdio.h>

long long p;

long long nrzero(long long n)
{
	long long p2, p5;
	p2 = p5 = 0;
	long long power;

	for(power = 2; n/power > 0; p2 += n/power, power *= 2);
	for(power = 5; n/power > 0; p5 += n/power, power *= 5);

	if(p2 < p5)
		return p2;
	return p5;
}

long long binary_search()
{
	long long st, dr;
	long long m, aux;
	long long keep = -1;

	st = 1;
	dr = 1000000000;

	while(st <= dr)
	{
		m = (st + dr)/2;

		aux = nrzero(m);

		if(aux == p)
		{
			keep = m;
			dr = m-1;
		}
		else if(aux < p)
		{
			st = m+1;
		}
		else if(aux > p)
		{
			dr = m-1;
		}
	}

	return keep;
}

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

	scanf("%lld\n", &p);

	if(p == 0)
		printf("0\n");
	else
		printf("%lld\n", binary_search());

	fclose(stdin);
	fclose(stdout);

	return 0;
}