Pagini recente » Cod sursa (job #1783415) | Cod sursa (job #2856748) | Cod sursa (job #2754229) | Cod sursa (job #801340) | Cod sursa (job #996165)
Cod sursa(job #996165)
#include <iostream>
#include <fstream>
#include <math.h>
#define min(x,y) (((x)<(y))?(x):(y))
using namespace std;
/* Using Legendre's theorem http://www.cut-the-knot.org/blue/LegendresTheorem.shtml */
long v(long n,int k) {
int r = 0;
long p = k;
while(p <= n) {
r += floor(n/p);
p *= k;
};
return r;
};
// returns the number of zeroes a factorial has at the end
long z(long n) {
return min(v(n,2),v(n,5));
};
/*
* Binary search for factorial
*/
long b(long p) {
long l,r;
l=0;
r=10000;
while(l<r) {
long m = (l + r)/2;
long zm = z(m);
//cout<<"m="<<m<<" zm="<<zm<<endl;
if(zm < p) {
l=m+1;
};
if(zm > p) {
r=m-1;
};
if(zm == p) {
for(long q=l;q<=r;q++)
if(z(q)==p)
return q;
return m;
};
};
return -1;
};
int main(){
ifstream I("fact.in");
ofstream O("fact.out");
long N;
I >> N;
O << (b(N));
return 0;
}