Pagini recente » Cod sursa (job #2539442) | Rating Hornai Vlad (HornaiVlad) | Cod sursa (job #2508237) | Cod sursa (job #3228013) | Cod sursa (job #2759850)
#include <fstream>
using namespace std;
///se cauta binar numarul N, in spatiul de solutii.
///pe N nu il generam, dar aflam puterea lui 5 din descompunerea lui, a.i. sa nu depasim limita memoriei.
///pentru fiecare N cautat : pcinci = puterea lui 5, din N!.
///daca pcinci == P, am terminat. pcinci < P, mergem pe stanga / analog dreapta. daca s > d, afisam -1.
///OPTIMIZARE :
/*
long long d = 33554432 : ~1.4sec;
cb :
if(s > d) return -1;
if(pcinci((s + d) / 2) == p) return ((s + d) / 2);
if(pcinci((s + d) / 2) < p) return cb(p, ((s + d) / 2) + 1, d);
if(pcinci((s + d) / 2) > p) return cb(p, s, ((s + d) / 2) - 1);
long long d = 33554432 : ~0.5sec;
cb :
if(s > d) return -1;
int pc = pcinci((s + d) / 2);
if(pc == p) return ((s + d) / 2);
if(pc < p) return cb(p, ((s + d) / 2) + 1, d);
if(pc > p) return cb(p, s, ((s + d) / 2) - 1);
long long d = 33554432 : ~0.5sec;
cb :
if(s > d) return -1;
int pc = pcinci((s + d) >> 1);
if(pc == p) return ((s + d) >> 1);
if(pc < p) return cb(p, ((s + d) >> 1) + 1, d);
if(pc > p) return cb(p, s, ((s + d) >> 1) - 1);
pc :
long long pcinci = 0;
for(int i = 1; i <= n; i++)
{
long long cop = i;
while(cop % 5 == 0)
{
pcinci++;
cop /= 5;
}
}
long long d = 33554432 : ~0.25sec;
cb identic,
pc : for(int i = 5; i <= n; i+=5)
*/
ifstream cin("fact.in");
ofstream cout("fact.out");
long long pcinci(long long n);
long long cb(long long p, long long s, long long d);
long long celmaimic(long long n);
int main()
{
long long p; cin >> p;
if(p == 0)
{
cout << 1;
return 0;
}
long long s = 1;
long long d = 33554432; /// nu e calculat, doar vreau sa vad punctaj
cout << celmaimic(cb(p, s, d));
return 0;
}
long long celmaimic(long long n)
{
while(n % 5 != 0)n--;
return n;
}
long long cb(long long p, long long s, long long d)
{
if(s > d) return -1;
int pc = pcinci((s + d) >> 1);
if(pc == p) return ((s + d) >> 1);
if(pc < p) return cb(p, ((s + d) >> 1) + 1, d);
if(pc > p) return cb(p, s, ((s + d) >> 1) - 1);
}
long long pcinci(long long n)
{
long long pcinci = 0;
for(int i = 5; i <= n; i+=5)
{
long long cop = i;
while(cop % 5 == 0)
{
pcinci++;
cop /= 5;
}
}
return pcinci;
}