Pagini recente » Cod sursa (job #1897049) | Cod sursa (job #2435045) | Cod sursa (job #1146263) | Cod sursa (job #1540564) | Cod sursa (job #840876)
Cod sursa(job #840876)
#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;
}