Cod sursa(job #2206522)

Utilizator memecoinMeme Coin memecoin Data 22 mai 2018 20:20:23
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
 
using namespace std;

int64_t n;

int64_t divisorsOf5(int64_t x) {
	int64_t result = 0;
	while (x > 0 && x % 5 == 0) {
		x /= 5;
		result++;
	}
	return result;
}

int64_t greatestMultiple(int64_t x) {
	int64_t result = 5;
	while (x > result * 5) {
		result *= 5;
	}
	return result;
}

int64_t zeroCount(int64_t x) {
	x -= x % 5;
	int64_t result = 0;
	while (x > 0) {
		int g = greatestMultiple(x);

		if (x % g == 0) {
			result += divisorsOf5(x);
			x -= 5;
		}
		else {

			int div = 5;
			while ((x % g) / div > 0) {
				result += (x % g) / div;
				div *= 5;
			}
			x -= x % g;
		}
	}
	
	return result;
}

int find(int64_t l, int64_t r, int64_t x) {
	if (l > r) {
		return -1;
	}

	int64_t mid = (l + r) / 2;
	int64_t value = zeroCount(mid);

	if (value == x) {
		return mid - mid % 5;
	} else if (value > x) {
		return find(l, mid - 1, x);
	} else {
		return find(mid + 1, r, x);
	}
}

int main() {
	freopen("fact.in", "r", stdin);
	freopen("fact.out", "w", stdout);

	scanf("%d", &n);

	int64_t upperBound = 10000;

	while (zeroCount(upperBound) < n) {
		upperBound *= 2;
	}

	int64_t x = find(1, upperBound, n);

	printf("%lld", x ? x : 1);

	return 0;
}