Cod sursa(job #996149)

Utilizator stefan.petreaStefan Petrea stefan.petrea Data 11 septembrie 2013 10:08:07
Problema Factorial Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#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;
        };
        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;
}