Cod sursa(job #63373)

Utilizator vmaneavmanea vmanea Data 28 mai 2007 00:12:28
Problema Factorial Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>

#include <values.h>

long long P, ok, N, maimic, maimare, i, p, minim;

long long P5[5555];

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

	scanf("%lld", &P);

	P5[0] = 1;

	minim = MAXLONG;

	for (i = 1; i <= 50; ++i)
		P5[i] = 5 * P5[i-1];

	for (N = 1; !ok; N <<= 1)
	{
		// calculez puterea p pentru N

		for (i = (p = 0) + 1; N / P5[i]; i++)
			p += N / P5[i];

		if (p >= P) ok = 1;
	}

	for (maimic = 1, maimare = N, N = (maimic + maimare) >> 1; 1;)
	{
		for (i = (p = 0) + 1; N / P5[i]; i++)
			p += N / P5[i];

		if (p == P)
		{
			if (N < minim) minim = N;

			maimare = N;

			N = (maimic + maimare) >> 1;
		}
		else if (P < p) // trebuie sa mai scad
		{
			maimare = N;

			N = (maimic + maimare) >> 1;
		}
		else
		{
			maimic = N;

			N = (maimic + maimare) >> 1;
		}

		if (maimic == N)
		{
		  if (N == maimare)
		  {
			for (i = (p = 0) + 1; N / P5[i]; i++)
				p += N / P5[i];

			if (p == P) if (N < minim) minim = N;

			break;
		  }
		  else if (N + 1 == maimare)
		  {
			N++;

			for (i = (p = 0) + 1; N / P5[i]; i++)
				p += N / P5[i];

			if (p == P) if (N < minim) minim = N;

			break;
		  }
		}


	}

	if (minim == 2000000000000000) minim = -1;

	printf("%lld\n", minim);

	return 0;
}