Pagini recente » Cod sursa (job #587252) | Cod sursa (job #1270096) | Cod sursa (job #2191981) | Cod sursa (job #55519) | Cod sursa (job #2797366)
//Lema:Pentru n natural si p si q numere prime cu p<q avem v_p(n!)>=v_q(n!)
//Dem lema: Rezulta imediat din formula lui Legendre
//Din lema trebuie sa aflam doar v_5(n!)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int legendre(int N, int p)
{
int s = 0, i=1;
while (pow(p, i) <= N)
{
s += N / pow(p, i);
i++;
}
return s;
}
int binarysearch(int st, int dr, long long P)
{
int mid = (st + dr) / 2;
if (legendre(mid, 5) == P)
return mid;
else if (legendre(mid, 5) > st)
dr = mid - 1;
else
st = mid + 1;
return -1;
}
int main()
{
ifstream fin("fact.in");
ofstream fout("fact.out");
int N = 1;
long long P;
fin >> P;
int st = 1, dr = INT32_MAX;
fout << binarysearch(st, dr, P);
}