Cod sursa(job #2334984)

Utilizator StefanSanStanescu Stefan StefanSan Data 3 februarie 2019 14:08:10
Problema Factorial Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

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

int power(long long int N, long long int P) {
	long long int r = 1;
	while (P)
	{
		if (P % 2 == 1)
			r = r * N;
		N = N * N;
		P = P / 2;
	}
	return r;
}
int legendre(long long int x) {
	long long int j = 1, sum = 0;
	while (power(5, j) <= x) {
		sum += x / power(5, j);
		j++;
	}
	return sum;
}
int main() {
	long long int n;
	in >> n;
	long long int v[30000];
	v[0] = 1;
	for (long long int i = n / 2; i < n * 10 ; i++) {
		v[i] = i * 5;
	}
	long long int sol = -1, left = 0, right = n * 10;
	while (left <= right) {
		long long int mid = (left + right) / 2;
		if (legendre(v[mid]) == n) {
			sol = v[mid];
			break;
		}
		if (legendre(v[mid]) > n) {
			right = mid - 1;
		}
		if (legendre(v[mid]) < n) {
			left = mid + 1;
		}
	}
	out << sol;
}