Pagini recente » Cod sursa (job #3196094) | Cod sursa (job #3219457) | Cod sursa (job #1457225) | Cod sursa (job #3269831) | Cod sursa (job #1660793)
/**
* Programul porneste de la urmatoarea observatie: pentru ca N! sa aiba P 0-uri, el trebuie sa aiba
* P 5-uri in descompunerea in factori primi, deoarece pentru fiecare 0 este necesar un 10 in produs,
* iar cum 10 = 2 * 5 si produsul va avea intotdeauna suficienti 2, conteaza doar numarul de 5-uri.
* Astfel, programul porneste cu N de la 0, adunand 0-uri (adica cate 5 la N) sau grupe de 6 0-uri
* (adica cate 25 la N), cand este posibil, pana cand numarul de 0-uri astfel obtinut este mai mare
* sau egal cu P. Daca numarul de 0-uri obtinut este mai mare decat P, programul va afisa -1, altfel
* va afisa N. De asemenea, la fiecare adunare, programul mai verifica pentru 5-uri suplimentare care
* pot aparea din obtinerea unui multiplu a unei puteri de 5 mai mare (de exemplu, 125, 625 etc.).
*/
#include <iostream>
#include <fstream>
using namespace std;
int P;
int N = 0;
int trailingZeros = 0; // numarul de 0-uri curent
void solve() {
while (trailingZeros < P) {
int aux;
// atunci cand se poate, programul aduna "grupe" de sase 0-uri pentru a scurta timpul de executie
if (trailingZeros + 6 < P) {
N += 25;
trailingZeros += 6;
aux = N / 25;
}
// altfel, aduna doar un 0
else {
N += 5;
aux = N;
}
// verificare pentru eventuale puteri mai mari ale lui 5
while (aux % 5 == 0) {
aux /= 5;
trailingZeros++;
}
}
// daca numarul de 0-uri gasit este mai mare decat P, inseamna ca nu exista raspuns pentru acest P
if (trailingZeros > P) {
cout << -1;
}
else {
cout << N;
}
}
int main() {
freopen("fact.in", "r", stdin);
freopen("fact.out", "w", stdout);
cin >> P;
// caz special pentru P = 0
if (P == 0) {
cout << 1;
return 0;
}
solve();
}