Cod sursa(job #1452473)

Utilizator GilgodRobert B Gilgod Data 20 iunie 2015 23:13:41
Problema Factorial Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <numeric>

#define MIN(a,b) ((a)<(b))?(a):(b)

const char IN[] = "fact.in", OUT[] = "fact.out";

using namespace std;

int P;

inline void read_data() {
	fscanf(fopen(IN, "r"), "%d", &P);
}

int perm_count_zeros(long long x) {
	int total = 0;
	long long cnt = -1;
	for (int b5 = 5; cnt != 0; b5 *= 5) {
		cnt = floor(x/b5);
		total += cnt;
	}
	return total;
}

inline int find_fact(int P) {
	if (P == 0) return 1;
	long long low = 1, high = 999999999LL;
	while (low < high) {
		long long m = low + (high - low) / 2;
		long long count = perm_count_zeros(m);
		if (count == P) {
			while (m % 5 != 0) --m;
			return m;
		}
		if (count < P) low = m + 1;
		else high = m - 1;
	}
}

int main() {
	read_data();
	fprintf(fopen(OUT, "w"), "%d\n", find_fact(P));
	return 0;
}