Pagini recente » Cod sursa (job #1791447) | Cod sursa (job #251545) | Cod sursa (job #2466519) | Cod sursa (job #1562637) | Cod sursa (job #22106)
Cod sursa(job #22106)
#include <stdio.h>
#include <math.h>
/* Intoarce floor de log5(n) */
inline int log5(long long n){
long long crt = 5;
int rez = 0;
while(crt <= n){
crt *= 5;
++rez;
}
return rez;
}
/* Calc numarul de zerouri ale lui n!
Mathworld: Z = sum(k=1:log5(n))(n/5^k)
*/
int trailingz(long long n){
int kmax = log5(n);
int z=0;
for(int k = 1 ; k <= kmax ; ++k){
z += (int)((long double)n / pow((long double)5,(long double)k));
}
return z;
}
/* Cauta numarul nr in vectorul v de lungime len
@returns: -1 daca nu a gasit, poz daca la gasit
*/
int search(int nr, int* v, int len){
int shift, k;
for(shift = 1 ; shift < len ; shift <<= 1);
for(k=0 ; shift > 0 ; shift >>= 1){
if((k | shift) < len && v[k | shift] <= nr)
k |= shift;
}
if(v[k] != nr)
return -1;
else
return k;
}
/* Cel mai mic numar natural care are P zerouri la sfarsit */
long long cmmFact(int p){
long long shift, k;
for(shift = 1 ; trailingz(shift) < p ; shift <<= 1);
for(k=0 ; shift > 0 ; shift >>= 1){
if(trailingz(k | shift) <= p)
k |= shift;
}
if(trailingz(k) != p)
return -1;
else{
int lastgood = k;
do{
--k;
if(trailingz(k) == p)
lastgood = k;
else
break;
}while(1);
return lastgood;
}
}
int main(){
freopen("fact.in","r",stdin);
freopen("fact.out","w",stdout);
int P;
scanf("%d",&P);
if(P == 0)
printf("1\n");
else
if(P == 1)
printf("5\n");
else
printf("%d\n",cmmFact(P));
return 0;
}