Cod sursa(job #2944225)

Utilizator ito726Petrescu Victor Gabriel ito726 Data 22 noiembrie 2022 10:58:33
Problema Factorial Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>

using namespace std;
ifstream fin("fact.in");
ofstream fout("fact.out");
long long P;
long long legendre(int k, long long n)
{
    long long p,numitor;
    p=0;
    numitor=k;
    while(n>=numitor)
    {
        p=p+n/numitor;
        numitor=numitor*k;
    }
    return p;
}
int bs(int st,long long dr)
{
    long long med,last=-1,k;
    bool ok=0;
    while(st<=dr)
    {
        med=st+(dr-st)/2;
        k=legendre(5,med);
        if(k==P)
        {
            ok=1;
            last=med;
            dr=med-1;
        }
        else
            if(k>P)
            {
                last=med;
                dr=med-1;
            }
            else
                st=med+1;
    }
    if(ok==0)
        return -1;
    return last;
}
int main()
{
    fin>>P;
    int ans;
    long long lim=1LL<<62;
    ans=bs(1,lim);
    fout<<ans;
    fin.close();
    fout.close();
    return 0;
}