Cod sursa(job #2197792)

Utilizator cosminionutCosmin Ionut cosminionut Data 22 aprilie 2018 21:30:51
Problema Factorial Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
#include <iostream>
#include <cmath>
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[1000], i, p;;
	memset(v, 0, 1000 * 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) {
	int st, dr, m, m_val, st_val, dr_val;

	st = 5;
	dr = N_MAX_APROX;
	st_val = puteri5(st);
	dr_val = puteri5(dr);
	m = 0;

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


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