Cod sursa(job #2367101)

Utilizator EdyOnuEdy Onu EdyOnu Data 5 martie 2019 08:34:01
Problema Factorial Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
// factorial.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

//#include "pch.h"
#include <utility>
#include <fstream>
#include <iostream>
#define RIGHT 500000

using std::ifstream;
using std::ofstream;
using std::cout;
using std::pair;

int P;

inline void readData() {
	ifstream{ "fact.in" } >> P;
}

inline int getFactors(long long x, int nr) {

	int factors = 0;

	while (x && x % nr == 0) {
		++factors;
		x /= nr;
	}

	return factors;
}

pair<int, int> decompose(long long number) {

	pair<int, int> zeros;

	for (long long element = number; element > 1; --element) {
		zeros.first += getFactors(element, 2);
		zeros.second += getFactors(element, 5);
	}

	return zeros;
}

long long getN(int P) {

	if (P == 0) {
		return 1;
	}

	int left = 0, right = RIGHT;

	while (left <= right) {
	
		long long nr = (left + right) >> 1;

		auto rez = decompose(nr);

		if (rez.second == P) {

			while (nr && nr % 5 != 0) {
				--nr;
			}
			
			return nr;
		}

		rez.second < P ? left = nr + 1 : right = nr - 1;
	}

	return -1;
}

int main(){
	readData();
	ofstream{ "fact.out" } << getN(P) << '\n';
	return 0;
}