Cod sursa(job #626937)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 28 octombrie 2011 17:31:57
Problema Factorial Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<fstream>
#include<iostream>
using namespace std;
unsigned short v[30000001];
void prelucrare()
{
	long i,y,c;
	for(i=5;i<=30000000;i=i+5) {
		y=i;
		c=0;
		while(y%5==0) {
			c++;
			y=y/5;
		}
		v[i]=c;
	}
}
long fact(long x)
{
	long c,i,y;
	c=0;
	for(i=5;i<=x;i=i+5) {
		y=i;
		while((y%5==0)&&(y>30000000)) {
			c++;
			y=y/5;	
		}
		c=c+v[y];
	}
	return c;
}
int main ()
{
	long p,q,m,c,a,n;
	ifstream f("fact.in");
	ofstream g("fact.out");
	f>>n;
	f.close();
	prelucrare();
	p=1;
	q=10000000;
	a=0;
	while(p<=q) {
		m=(p+q)/2;
		c=fact(m);
		if(c<n)
			p=m+1;
		else if(c>n) 
			q=m-1;
		else {
			a=1;
			break;
		}
	}
	if(a==0)
		g<<"-1";
	else {
		while(m%5!=0)
			m--;
		if(m==0)
			m++;
		g<<m;
	}
	g.close();
	return 0;
}