Cod sursa(job #2797366)

Utilizator Cyf0Spineanu Rares Cyf0 Data 9 noiembrie 2021 19:32:22
Problema Factorial Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
//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);
}