Cod sursa(job #188839)

Utilizator laplaceConstantin Macari laplace Data 10 mai 2008 03:15:45
Problema Factorial Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 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 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;
       while(i){
                c=(a+b)/2;  
                if(ten(c)==n&&a==b){
                              i=a;
                              break;  
                              }
                if(b<a){
                        i=-1;
                        break;
                        }
                if(ten(c)<n)
                            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;  
   }