Cod sursa(job #2197812)

Utilizator cosminionutCosmin Ionut cosminionut Data 22 aprilie 2018 21:57:35
Problema Factorial Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;

ifstream f("fact.in");
ofstream g("fact.out");

int P;
int N;

#define N_MAX_APROX 381000000


void test(int p) {
	// naiv
	unsigned long long prod = 1;
	unsigned long long i = 1;
	unsigned long long P = (unsigned long long)pow(10, p);
	while (i < 50) {
		cout << prod << "\n";
		if (prod % P == 0) {
			cout << i << "\n";
			break;
		}
		i += 1;
		prod *= i;
	}
}

void a(int p) {
	// testeaza numere din 5 in 5
	if (p == 0)
		g << 1 << " \n";
	else {
		int count = 0;
		int x, aux;
		for (x = 0; count < p;) {
			x += 5;
			aux = x;
			while (aux % 5 == 0) { aux /= 5; count++; }
		}
		g << x << "\n";
	}
}

int puteri5(int n) {
	int v[15], i, p;;
	memset(v, 0, 15 * sizeof(int));

	for (i = 1, p = 5; p <= n; i++, p*=5)
		v[i] = n / p;

	for (i = 2; v[i] != 0; i++)
		v[1] += v[i] * (i - 1);

	return v[1];
}


int minN(int P) {
	if (P == 0)
		return 1;

	int st, dr, m, m_val;

	st = 5;
	dr = N_MAX_APROX / 4;
	m = 0;

	while (true) {
		if (st == dr)
			return st / 5 * 5;
		else {
			m = (st + dr) / 2;
			m_val = puteri5(m);
			if (m_val == P) {
				return m / 5 * 5;
			}
			else if (m_val > P) {
				dr = m - 1;
			}
			else if (m_val < P) {
				st = m + 1;
			}
		}
	}
}


int main() {
	f >> P;
	g << minN(P);
	return 0;
}