Cod sursa(job #187860)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 5 mai 2008 17:52:32
Problema Factorial Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
/*

 1. Numarul de zerouri finale ale numarului n! este dat de suma

        z = [n/5]+[n/25]+[n/125]+...

 2. O legatura intre n si z poate fi relatia

        s(p, n) = n - (p-1)*z

    unde p este baza de numeratie in care se reprezinta n, iar s(p, n)
    este suma cifrelor reprezentarii lui n in aceasta baza;

    Deoarece factorii 5 sunt mai putini decat factorii 2, am hotarat
    sa alegem p=5 si sa gasim un n > 4*z (fara a cauta la infinit !)
    pentru care numarul t calculat conform relatiei 1 coincide cu z (dat)

*/

#include <stdio.h>

long int nr_zerouri(long int n) {
 long int w, q=5, r=0;
 while(w=n/q) {r += w; q *= 5;}
 return r;
}

int main() {
 long int z, t, n, f=0;
 freopen("fact.in", "r", stdin);
 freopen("fact.out", "w", stdout);
 scanf("%ld", &z);
 
 for(n=z*4; (n<z*5) && (f==0); n+=5) {
  t=nr_zerouri(n); if (t==z) f=1;
 }
 if(!z){f=1;n=1;}
 if(f) printf("%ld\n", n); else printf("-1\n");
 return 0;
}