Cod sursa(job #896439)

Utilizator valiro21Valentin Rosca valiro21 Data 27 februarie 2013 15:40:52
Problema Factorial Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>

using namespace std;

long p,px,pw,pw2,v[14];
long long n;

int bsearchMin(long in,long fn,long v[],long val) {
    long mid;
    if(v[fn]<=val)
        return fn;
    else
        if(val<v[1])
            return 0;

    while(in<=fn) {
        mid=(fn-in)/2+in;
        if(v[mid]<=val&&val<v[mid+1])
            return mid;
        else
            if(val<v[mid])
                fn=mid-1;
            else
                in=mid+1;
    }
    return 0;
}

int lgpow(long base,long pw) {
    long rez=1;
    while(pw) {
        if(pw%2)
            rez*=base;
        base*=base;pw/=2;
    }
    return rez;
}

int main()
{
    freopen("fact.in","rt",stdin);
    freopen("fact.out","wt",stdout);
    scanf("%ld",&p);
    if(p==0) {
        printf("1\n");
        return 0;
    }

    pw=1;
    for(long i=1;i<=12;i++) {
        pw*=5;pw2=5;
        while(pw2<=pw)
            v[i]+=pw/pw2,pw2*=5;
    }

    n=0;
    while(p) {
        px=bsearchMin(1,12,v,p);
        p-=v[px];
        n+=lgpow(5,px);
    }

    printf("%ld\n",n);

    return 0;
}