Cod sursa(job #201124)

Utilizator pitbullpitbulll pitbull Data 29 iulie 2008 04:10:33
Problema Factorial Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>

#define in_file "fact.in"
#define out_file "fact.out"
#define NMAX 10000000

int n,res;
int div2[NMAX];
int div5[NMAX];


int nr_div(int n,int div){
	int nr=0;
	while(n%div==0){
		n/=div;
		nr++;
	}
	return nr;
}

long long int nr_zerouri(int n){
	long long int nr2=0,nr5=0,res=0,i=0;
	
	
	for (i=2;i<=n;i+=2){
		if(div2[i]<0)
			div2[i]=nr_div(i,2);
		nr2+=div2[i];
	}
	
	for (i=5;i<=n;i+=5){
		if(div5[i]<0)
			div5[i]=nr_div(i,5);
		nr5+=div5[i];
	}
	
	res=nr2<nr5?nr2:nr5; 
	
	return res;
}



int find(int n){
	int low=0,high=NMAX-1,mid=0;
	long long int nrz;
	while(low<=high){
		mid=low+(high-low)/2;
		nrz=nr_zerouri(mid);
		
		if(nrz==n){
			while(nr_zerouri(mid-1)==nrz&&mid>=2)
				mid--;
			return mid;
		}
		else if(nrz<n)
			low=mid+1;
		else
			high=mid-1;
	}
	return -1;
}



int main (){
	FILE *f=fopen(in_file,"rt");
	fscanf(f,"%d",&n);
	fclose(f);
	
	int i;
	for (i=0;i<NMAX;i++)
		div2[i]=div5[i]=-1;
	
	
	res=find(n);
	
	FILE *g=fopen(out_file,"wt");
	fprintf(g,"%d",res);
	fclose(g);
	return 0;
}