Wypisywanie liczby zer, którymi kończy się liczba n! - problem z szybkością działania.

Witam serdecznie,

mam taki problem z pewnym zadaniem ze SPOJA(kategoria ŁATWE):

Wejście

Mamy t testów, t < 100000. Każdy test składa się z jednej liczby n < 1 073 741 824.

Wyjście

Dla każdej liczby n wypisać liczbę zer, którymi kończy się liczba n!.

Maksymalny czas wykonania:

1s.

Napisałem dwa programy jeden z użyciem iostreamu, to wyskakuje, że program za wolny:

    #include<iostream>
    #include <math.h>
     
    using namespace std;
    int main ()
    {
    int suma=0,n;
    double liczba;
    cin>>n;
    for(int i=0;i<n;i++)
    {
     
    cin>>liczba;
    double l1=log(liczba);
    double l2=log(5.0);
    double max=floor(l1/l2);
    for(int k=1;k<max+1;k++)
    {
    suma+=floor(liczba/pow(5.0,k));
    }
    cout<<suma;
suma=0;
    }
     
     return 0;
    }
 

a jak zmieniłem na bibliotekę cstdio to niby daje złe wyniki:

     #include <math.h>
    #include<cstdio>
    int main ()
    {
    int suma=0,n;
    float liczba;
    scanf("%u",&n);
    for(int i=0;i<n;i++)
    {

    scanf("%f",&liczba);
    float l1=log(liczba);
    float l2=log(5.0);
    float max=floor(l1/l2);
    for(int k=1;k<max+1;k++)
    {
    suma+=floor(liczba/pow(5.0,k));
    }
    printf("%d\n",suma);
suma=0;
    }

Proszę o pomoc, co jest w nich źle i jak to napisać dobrze? Z góry dziękuję za pomoc :)

PS. Wzór na liczbę zer, jakimi kończy się n!:

zapomnij o log i o pow, bo zbędne i szkodliwe

to w jaki inny sposób obliczać potęgi i logarytmy bez log i pow?! :O

To jest z polskiego spoja? Nie widzę tu takiego zadania.

Co do samego algorytmu:
http://www.mytechinterviews.com/how-many-trailing-zeros-in-100-factorial

Wystarczy pogooglować.

owszem polski SPOJ :)

dziel liczbę n przez 5 tak długo aż ją wyzerujesz, wyniki z dzielenia dodawaj do wyniku. powinno to zająć kilka linijek.

na przykład:
30/5 = 6
6/5 = 1
wynik 6+1=7

Dzielenie przez 5 działa, ale nie dla całego zakresu liczb. Tutaj: http://www.matematyka.pl/16471.htm opisano algorytm na rozwiązanie problemu. Zakodowałem to w ten sposób:

pom=floor(x/5);
pom=pom+floor(x/25);
printf("%.0f\n",floor(pom)); 

Działa, ale dla dużych liczb są różnice z tym co liczę "na piechotę" (w excelu ;) ), prawdopodobnie jest to problem zaokrąglania liczb (np. dla 1.000.000 wg. linku powyżej wychodzi: 249988 zer, wg. programu i liczenia na piechotę: 240000; dla kolejnego testu dla liczby: 987654321 wg. liczenia na piechotę wychodzi 237 037 037 zer, wg powyższego kodu: 237037040 - jaki jest prawidłowy wynik nie wiem). Jakby ktoś rozwiązał problem to niech wrzuci podpowiedź ;)

nie zapisuj liczby jako float tylko jako int!!!

lz(         10)=2
lz(        100)=24
lz(       1000)=249
lz(      10000)=2499
lz(     100000)=24999
lz(    1000000)=249998
lz(   10000000)=2499999
lz(  100000000)=24999999
lz(  987654321)=246913573
lz( 1000000000)=249999998
lz(10000000000)=2499999997

lz(2^{2011)=5.878429159804183164072105834 *10}603

int ilosc_zer(int n)
{
  int wynik = 0;
  while (n)
    {
      n/=5;
      wynik+=n;
    }
  return wynik;
}

krwq, Twoja metoda zadziałała, trzeba było dodać pewną rzecz, ale dziękuję bardzo :)

Było:

int lzA(int n){
    return n>>(('/'/'/')<<1) - rand()%(1<<(1<<`code>Miało być:`int lzA(int n){
    return (n>>('/'/'/'<<1)) - rand()%(1<<(1<<`code>Ale niech będzie:`int lzA(int n){
    return (n>>('/'/'/'<<1)) ;}