Cod sursa(job #579838)

Utilizator BlackElfSpulber Iosif BlackElf Data 12 aprilie 2011 15:13:02
Problema Factorial Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <iostream>
#include <fstream>

using namespace std;

int pws[]={5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125,244140625,1220703125};

int noOfFives (int n)
{
	/*int c = 0;
	int i = 0;
	int a = 1;

	while (a)
	{
		a = n / pws[i];
		c += a;
		i ++;
	}

	return c;*/

	long s=0;
	s+=n/5;
	s+=n/25;
	s+=n/125;
	s+=n/625;
	s+=n/3125;
	s+=n/15625;
	s+=n/78125;
	s+=n/390625;
	s+=n/1953125;
	s+=n/9765625;
	s+=n/48828125;
	s+=n/244140625;
	s+=n/1220703125;
	return s;
}

int main ()
{
	ifstream in ("fact.in");
	ofstream out ("fact.out");

	int p;
	int n = 5;
	int nfv;
	int left, right;

	in >> p;

	if (p == 0)
	{
		out << 1 << endl;
		return 0;
	}

	if (p < 0)
	{
		out << -1 << endl;
		return 0;
	}
	

	left = 0;
	right = p * 5;

	while (1)
	{
		n = (left + right) / 2;
		nfv = noOfFives(n);

		if (nfv < p)
			left = n;
		else
			if (nfv > p)
				right = n;
			else
			{
				n-=1000;
				 if (n<=0) n=1;
				 for (;noOfFives(n)<p;n++);
				 if (noOfFives(n)!=p) cout << -1 << endl;
				out << n << endl;
				return 0;
			}
	}

	return 0;
}