Pagini recente » Cod sursa (job #1366133) | Cod sursa (job #1824465) | Cod sursa (job #1857203) | Cod sursa (job #2744519) | Cod sursa (job #870424)
Cod sursa(job #870424)
#include <fstream>
#include <cmath>
using namespace std;
//Acest vector retine primele 12 puteri ale lui 5, inclusiv 5^0=1
int puteri_5[]={1,5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125,244140625,1220703125};
//Aceasta functie determina cati de 0 are x! la sfarsit
long long int nr_factori_10(long long int x)
{
long long raspuns=0;
while(x>=5)
{
raspuns+=x/5;
x/=5;
}
//Intoarcem raspunsul
return raspuns;
}
long long exp(int k)
{
long long y=0;
while(k>=5)
{
y=y+k/5;
k=k/5;
}
return y;
}
int main()
{
//Deschidem fisierele de intrare si iesire
ifstream fin("fact.in");
ofstream fout("fact.out");
//P-ul din enunt
int p;
//Citim numarul de 0-rui cerut
fin>>p;
//Daca acesta este 0, nu putem afisa 0 (caci 0!=1, dar 0 nu este strict pozitiv), ci 1
if(p==0)
{
fout<<"1\n";
//Inchidem fisierele de intrare si iesire
fin.close();
fout.close();
return 0;
}
//Cautam binar valoarea ceruta
long long int cap=1; //Se pleaca de la 1!=1
long long int coada=5*p; //La (5*p)!, caci acesta are sigur minim p de 0 la sfarsit (din Formula lui Legendre)
long long int mijl=(cap+coada)/2;
//In rezultat vom tine cel mai mic rezultat obtinut
long long int rezultat=-1;
//Cautarea binara propriu-zisa
while(cap<=coada)
{
//Daca are fix p de 0 la sfarsit, verificam daca poate fi solutie
if(nr_factori_10(mijl)==p)
{
if(mijl<rezultat || rezultat==-1)
rezultat=mijl;
coada=mijl-1;
}
else if(nr_factori_10(mijl)>p) //Daca nu are, avem cele doua cazuri clasice ale cautarii binare
{
coada=mijl-1;
}
else
{
cap=mijl+1;
}
//Facem update la mijloc
mijl=(cap+coada)/2;
}
//Afisam rezultatul
fout<<rezultat<<'\n';
//Inchidem fisierele de intrare si iesire
fin.close();
fout.close();
return 0;
}