Cod sursa(job #218864)

Utilizator SliMMStefan Saftescu SliMM Data 3 noiembrie 2008 20:38:17
Problema Factorial Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
/*
 * factorial.cpp
 *
 *  Created on: Nov 2, 2008
 *      Author: stefan
 */

#include<stdio.h>

unsigned long int numberOfZeros(const unsigned long int factorial)
{
	unsigned long int number = 0;
	for (unsigned long int p = 5; p <= factorial; p *= 5)
	{
		number += factorial / p;
	}

	return number;
}

int main()
{
	unsigned long int P;
	register unsigned long int min = 1, max = 80000003L, mid, no;

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

	scanf("%lu", &P);

	if (P == 0)
	{
		printf("1");
		return 0;
	}

	while (min != max)
	{
		if ((no = numberOfZeros(5 * (mid = (min + max) / 2))) > P)
		{
			max = mid;
		}
		else if (no < P)
		{
			if (min != mid)
				min = mid;
			else
				max = mid;
		}
		else
		{
			printf("%lu", 5 * mid);
			return 0;
		}
	}

//	for (N = 5; P > 0; N += 5)
//	{
//		i = N;
//		while (i % 5 == 0)
//		{
//			--P;
//			i /= 5;
//		}
//	}

	if (numberOfZeros(5 * mid) != P)
		if (numberOfZeros(5 * max) != P)
			printf("-1");
		else
			printf("%lu", 5 * max);
	else
		printf("%lu", 5 * mid);

//	printf("%lu", numberOfZeros(P));
	return 0;
}