Cod sursa(job #701356)

Utilizator ephgstefana gal ephg Data 1 martie 2012 15:26:07
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
int p5[50],a[50],dim;

int rez(int n){
	int i,c=0;
	for(i=1;p5[i]<=n;++i){
		c+=n/p5[i];
	}
	return c;
}

void cb(int nr,int putere){
	int ls,ld,m,ma;
	ls=p5[putere];
	ld=p5[putere+1];
	for(;ls<ld;){
		ma=m;
		m=(ls+ld)/2;
		if(ma==m)break;
		//fprintf(stderr,"%d %d %d",ls,m,ld);
		if(rez(m)<=nr)ls=m;
		else ld=m-1;
	}
	for(;ls%5!=0;--ls){}
	
	if(rez(ls)==nr)printf("%d\n",ls);
	else printf("-1");
}
int main () {
	int n,i,c=0,vc,uv,j;
	
	freopen("fact.in","r",stdin);
	freopen("fact.out","w",stdout);
	scanf("%d",&n);
	if(n==0){
		printf("1");
		return 0;
	}
	for(i=1;i<=14;++i){
		if(dim==0)p5[++dim]=5;
		else {
			if((dim+1)%2==0)p5[++dim]=p5[dim/2]*p5[dim/2];
			else p5[++dim]=p5[dim/2]*p5[dim/2]*5;
		}
		
	}
	
	//for(i=1;i<=25;++i)fprintf(stderr,"%d ",p5[i]);
	a[1]=1;
	for(i=2;i<=dim;++i)a[i]=a[i-1]*5+1;
	for(i=1;a[i]<=n;++i){}
	--i;
	cb(n,i);
	
	return 0;
}