Cod sursa(job #188836)

Utilizator laplaceConstantin Macari laplace Data 10 mai 2008 02:42:01
Problema Factorial Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
   /*Se da un numar intreg P. Sa se gaseasca cel mai mic numar natural strict  
   pozitiv N pentru care N! are exact P cifre de 0 la sfarsit. 
    
   Se stie ca N! = 1 * 2 * 3 * .... * (N - 1) * N. 
   Exemplu : 0 --> 1 
             2 --> 10 
             10 --> 45*/  
     
   #include<stdio.h>  
   #include<stdlib.h>  
     
   const long MAX=100000*100000;  
     
   long n;  
     
   long factor(long m){  
        if (0 == m)  
           return 1;  
        else  
            return (m * factor(m-1));  
   }  
     
   long ten( long c ){
        long p = 0;
        while( c ){
                   p += c/5;
                   c /= 5;
                   }
        return p;  
   }     
     
   long fact(long a,long b,long n){  
        int i=1;
        long c=0L;
        long nrz=0L;
        while(i){
                 c=(a+b)/2;
                 nrz=ten(factor(c));
                 if(nrz==n&&a==b){
                                  i=a;
                                  break;
                                  } 
                 if(b<a){
                         i=-1;
                         break;
                         } 
 	             if(n>nrz)
                          a=c+1;
 	             else
                     b=c-1;                            
                 }
        return c;  
   }  
     
   int main(){  
       freopen("fact.in","r",stdin);  
       freopen("fact.out","w",stdout);  
       scanf("%ld",&n);  
       long a=0L;long b=MAX; 
       if(n==0){
                printf("%d",1); 
                exit(0);
                }
       long rez=fact(a,b,n);  
       if(rez)  
              printf("%ld",rez);  
       else(printf("%d",-1));  
       return 0;  
   }