Cod sursa(job #2772645)

Utilizator Darius_CDarius Chitu Darius_C Data 1 septembrie 2021 23:16:36
Problema Factorial Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 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 x)
{
	ll rez = 0;
	for (ll pow5 = 5; pow5 <= x; pow5 *= 5)
		rez = rez + x / pow5;
	return rez;
}

void BinarySearch()
{
	ll st = 0, dr = INF;
	ll N;
	if (P == 0)
		N = 1;
	else
		while (st <= dr)
		{
			ll mij = (st + dr) / 2;
			ll zeros = Zero_Factorial(mij);
			if (zeros == P) {
				N = mij;
				dr = mij - 1;
			}
			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;
}