Cod sursa(job #1652214)

Utilizator avneacsuAlexandra Neacsu avneacsu Data 14 martie 2016 19:35:07
Problema Factorial Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

long factorial(int n) {
	if (n == 0 || n ==1)
		return 1;
	else return n * factorial(n-1);
}

long smallestNo(int p) {
	if (p == 0)
		return 1;

	long output = 0;
	long multipliesFound = 0;

	while (multipliesFound < p) {
		output++;

		if (output%625 == 0) {
			multipliesFound += 5;

			long temp = output/625;
			long multiplies = 0;
			while (temp%5 == 0) {
				multiplies++;
				temp = temp/5;
			}
			multipliesFound += multiplies;

		} else if (output%125==0) multipliesFound += 4;
		else if (output%25==0) multipliesFound += 3;
		else if (output%5==0) multipliesFound += 2;
		else multipliesFound += 1;
	}

	output *= 5;

	if (multipliesFound > p) output = -1;
	return output;
}

long long pow5(long exp) {
	if (exp == 0) return 1;
	else return 5 * pow5(exp-1);
}

long float log_5(long float x) {
	return log(x) / log(5.0);
}

long trailingZeros(long n) {
	long k = floor((float) log_5(n));

	long acc = 5;
	long output = 0;
	for (int i = 1; i <= k; i++) {
		output += floor((float) n/acc);
		acc *= 5;
	}

	return output;
}


long factSearch(long p) {
	int k = 1;
	int sum = 1;
	int prevSum = 1;

	while (sum < p) {
		long aux = sum;
		sum = sum*5 + 1;
		prevSum = aux;
		k++;		
	}
	
	if (sum == p) {
		return pow5(k);
	}
	
	long long left = pow5(k-1), right = pow5(k);
	long leftCount = trailingZeros(left), rightCount = trailingZeros(right);

	while (left != right && left < right) {
		long long middle = (left + right)/2;
		long middleCount = trailingZeros(middle);

		if (middle == left) 
			break;
		if (middleCount == p)
			return middle;
		else if (middleCount < p) {
			left = middle;
			leftCount = middleCount;
		} else {
			right = middle;
			rightCount = middleCount;
		}

		
		//cout<<left<<" "<<middle<<" "<<right<<endl;
	}

	if (leftCount != p)
		return -1;
	else return left;
}

int main(void) {
	ifstream f("fact.in");
	ofstream g("fact.out");
	long p;
	f>>p;
	long output = factSearch(p);
	g<<output;
	return 0;
}