Cod sursa(job #408561)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 3 martie 2010 08:55:19
Problema Factorial Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <vector>
// pt debug
#include <string>
#include <sstream>
using namespace std;

ifstream in("fact.in");
ofstream out("fact.out");

vector<long long> p2;
long long li, ls, n, p, k;

// pt debug
string show_v(vector<long long> x)
{
    stringstream s;
    s<<"[ ";
    for(vector<long long>::iterator it = x.begin(); it!=x.end(); it++)
        s<<*it<<' ';
    s<<']';
    return s.str();
}

long long fact(long long x)
{
    vector<long long>::reverse_iterator it = p2.rbegin();
    long long ret = 0;
    for(; it!=p2.rend(); it++)
        if(x>=*it)
        {
            ret += (x/ *it);
        }
    return ret;
}

int main()
{
    in>>p;
    k=5;
    while(k < 10000000000LL)
    {
        p2.push_back(k);
        k*=5;
    }

    li = 0;
    ls = 10000000000LL;

    fact(40);

    while(k = fact((li+ls)/2))
    {
        if(k==p)
            {out<<(((li+ls)/2)/5)*5;return 0;}
        if(k<p)
            li=(li+ls)/2+1;
        else
            ls=(li+ls)/2-1;
    }
    out<<0;

    return 0;
}