Cod sursa(job #778292)

Utilizator predator5047Butiu Alexandru Octavian predator5047 Data 14 august 2012 13:53:38
Problema Factorial Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
//============================================================================
// Name        : Factorial.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <fstream>
using namespace std;

typedef unsigned long long ull;

ull get_zero_count(ull n) {
	ull sum = 0;

	for(ull i = 5; i <= n; i *= 5)
		sum += n / i;

	return sum;
}

ull bsearch(ull target) {

	ull low = 1, high = 800000000, mid;

	while(low <= high) {
		mid = (low + high) / 2;

		ull zero_count = get_zero_count(mid);

		if(zero_count > target)
			high = mid - 1;
		else if(zero_count < target)
			low = mid + 1;
		else
			return mid;

	}

	return -1;
}

int main() {

	ull p;

	ifstream fin("fact.in");
	ofstream fout("fact.out");
	fin >> p;

	if(p == 0) {
		fout << 1;
		return 0;
	}
	ull k = bsearch(p);

	if(k % 5)
		fout << k - k % 5;
	else
		fout << k;


	fin.close();
	fout.close();



	return 0;
}