Cod sursa(job #840876)

Utilizator dm1sevenDan Marius dm1seven Data 23 decembrie 2012 13:17:30
Problema Factorial Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
using namespace std;
#include <fstream>

namespace pb_006_factorial_nms
{
	int f(int p, int N)
	{
		int t = N;
		int power = 0;
		while (t = t/p) power += t;	

		return power;
	}
}
//int pb_006_factorial()
int main()
{
	using namespace pb_006_factorial_nms;
	char* in_file = "fact.in";
	char* out_file = "fact.out";

	int P;

	ifstream ifs(in_file);
	ifs>>P;
	ifs.close();

	int MAX_N = 100000000;	
	int a = 1, b = MAX_N;
	
	int f_a = f(5, a), f_b = f(5, b), f_bm1 = f(5, b-1), f_m;
	//binary search
	while ( !(f_bm1 < P && P <= f_b) ) //f(b-1) < P <= f(b) is the end condition
	{
		int m = (a+b)/2;
		f_m = f(5, m);
		if (f_m < P) { a = m; f_a = f_m; }
		else /* P <= f_m */ { b = m; f_b = f_m; f_bm1 = f(5, b-1); }		
	}

	ofstream ofs(out_file);
	ofs<<b;
	ofs.close();

	return 0;
}