Cod sursa(job #2713530)

Utilizator mariusn01Marius Nicoli mariusn01 Data 28 februarie 2021 10:56:04
Problema Factorial Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>

using namespace std;
int prod, i, j, nrZero, p;

ifstream fin ("fact.in");
ofstream fout("fact.out");

int main () {
    fin>>p;
    for (i=1;;i++) {
        /// cati de 0 are la final i!

        /// un 0 de la final se obtine dintr-un produs 2*5
        /// deci ne intereseaza la ce putere apare 2 in descompunerea
        /// produsului 1*2*...*i
        /// si la ce putere apare 5 in descompunerea in factori primi a acestui
        /// produs. Solutia e data de minimul dintre exp lui 2 si exp lui 5
        /// Fiind vorva de toate numerele de la 1 la i, 2 apare mai des decat 5
        /// deci ne intereseaza la ce putere apare 5 in pridusul 1*2*...i
        /**
        la ce putere apare 5 in 131!
        R: [131/5] + [131/5 la a doua] + [131/5 la a treia] si ma opresc
        pentru 5 la a patra e deja mai mare ca 131 si 131/5 la a patra face 0

        [131/5] = cate numere sunt divizibile cu 5 (in cate numere apare 5)
        [131/5 la a doua] = cate numere au inca un 5 (25, 50, 75, 100, 125)
        [131/5 la a treia] = cate numere au si al treilea 5 (125)
        **/
        nrZero = 0;
        int p5 = 5;
        while (p5 <= i) {
            nrZero += i/p5;
            p5 *= 5;
        }
        if (nrZero == p)
            break;
    }
    fout<<i;
}