Cod sursa(job #996168)

Utilizator stefan.petreaStefan Petrea stefan.petrea Data 11 septembrie 2013 11:19:13
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <math.h>

#define min(x,y) (((x)<(y))?(x):(y))
#define max(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,long k) {
    long 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=1;
    r=2000000000;
    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;
}