Cod sursa(job #2857543)

Utilizator Darius_CDarius Chitu Darius_C Data 25 februarie 2022 19:40:07
Problema Factorial Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
// Factorial.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>
#define INF 0x3F3F3F3F
std::ifstream fin("fact.in");
std::ofstream fout("fact.out");
using namespace std;
typedef long long ll;

ll P;

int Zero_Factorial(ll n, ll p)
{
	// Formula Legendre / dePolignac
	ll rez = 0;
	while (n)
	{
		rez += n / p;
		n /= p;
	}
	return rez;
}

void BinarySearch()
{
	ll st = 0, dr = INF;
	ll N = -1;
	if (P == 0)
		N = 1;
	else
		while (st <= dr)
		{
			ll mij = (st + dr) / 2;
			ll zeros = Zero_Factorial(mij, 5);
			if (zeros == P) {
				// Respecta conditia
				N = mij;
				dr = mij - 1; // Cautam o valoare mai mica care respecta conditia
			}
			else if (zeros > P)
				dr = mij - 1;
			else
				st = mij + 1;
		}
	fout << N;
}

int main()
{
	fin >> P;
	// Cautare binara discreta pe variabila N astfel incat Zero_Factorial(N)==P
	BinarySearch();
	return 0;
}