Pagini recente » Cod sursa (job #2012360) | Cod sursa (job #965514) | Cod sursa (job #1594328) | Cod sursa (job #1768090) | Cod sursa (job #201119)
Cod sursa(job #201119)
#include <stdio.h>
#define in_file "fact.in"
#define out_file "fact.out"
#define NMAX 2200000
int n,res;
int v[NMAX];
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;
}
int nr_zerouri(int n){
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 nrz,low=1,high=NMAX-1,mid=0;
while(low<=high){
mid=low+(high-low)/2;
if(v[mid]>=0)
nrz=v[mid];
else{
nrz=nr_zerouri(mid);
v[mid]=nrz;
}
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++)
v[i]=div2[i]=div5[i]=-1;
res=find(n);
FILE *g=fopen(out_file,"wt");
fprintf(g,"%d",res);
fclose(g);
return 0;
}