SPOJ - Kartkówka(KART)

Question

Zmagam się z zadaniem "Kartkówka" z platformy SPOJ:

                                     http://pl.spoj.com/problems/KART/

Wydawało mi się,

że problem jest bardzo podobny do zadania, w którym wyświetlić należało dwie ostatnie cyfry silni. Obliczyłem w arkuszu wartości silni dla niektórych liczb i próbowałem szukać jakiegoś związku. Nietrudno było zauważyć, że w przedziale <0, 4> wartości silni nie kończą się zerem, w przedziale <5, 9> kończą się jednym zerem, w przedziale

<10, 14> dwoma zerami, a dla 15 liczba zer na końcu zwiększa się do trzech. Wydawało mi się, że wobec tego wystarczy podzielić liczbę z wejścia przez 5 i wynik tej operacji okaże się być szukaną liczbą zer. Otrzymałem jednak komunikat o błędnej odpowiedzi, chociaż akurat dla przypadków testowych podanych w zadaniu program działał poprawnie.

Czy ktoś mógłby mi podpowiedzieć, co jest nie tak z moim rozumowaniem? Chyba że błąd leży w kodzie, ale to wydaje mi się mniej prawdopodobne(wrzucam cały kod, bo jest bardzo krótki).

#include<iostream>

int main()
{
	 int t;

	std::cin >> t;

	while (t--)
	{
		long long int n;
		std::cin >> n;

		long long int result;
		
		result = n / 5;

		std::cout << result << "\n";
	}


	return 0;
}

 

Comments

25! = ... 000000 - 6 zer

25 / 5 = 5

5 != 6

---

Faktycznie, ale jakoś nie potrafię się domyślić, dlaczego kolejne zero pojawiło się akurat w tym miejscu.

Edit: dodatkowe zero dla 25, 50, 75, 100? Ale nie wiem co dalej, bo nie mogę znaleźć tak dużej tabelki bez notacji naukowej.

---

n moze byc rowne nawet 1073741823 :D

---

Nie rozumiem tej uwagi :/. W unsigned long long chyba i tak się zmieści, a póki co dostaję błędną odpowiedź, a nie przekroczenie limitu czasu. Nie wiem, kiedy dokładnie pojawiają się zera.

---

zmiesci sie w double

---

Nie zmieści sie w double, double nie ma nieograniczonego wykladnika

---

Chodzilo mi o n a nie n!

Answer 1

Zadanie jest odrobinę matematyczne i polega na takiej obserwacji:
Rozłóżmy na czynniki pierwsze 10: 2 * 5
Rozłóżmy na czynniki pierwsze 10!:
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = ( 2 ) * ( 3 ) * ( 2 * 2 ) * ( 5 ) * ( 2 * 3 ) * ( 7 ) * ( 2 * 2 * 2 ) * ( 3 * 3 ) * ( 2 * 5 ) = 
2^8 * 5^2 * 3^4 * 7 = ( 2^2 * 5^2 ) * 2^6 * 3^4 * 7 = 10^2 * 2^6 * 3^4 * 7
Wnioski:
Silnia ma tyle zer na końcu, ile można dobrać par 2 i 5  w rozkładach na czynniki pierwsze liczb od 1 do 'ostatnia_liczba_silni'

Czyli wystarczy wziąć minimum z ilości 2 i ilości 5 w rozkładach, bo tyle jest par.

To dopiero część rozwiązania, bo trzeba policzyć ile jest 2 i 5 w tych rozkładach.
W tym momencie zachęcam do poprowadzenia tego dalej, ale na wszelki wypadek napisze
jak zrobić całe zadanie i potem dołączę kod, jeśli nie wymyślisz reszty to będziesz mógł przeczytać, zachęcam do popróbowania samemu

Jak policzyć ile jest dwójek w rozkładach na czynniki pierwsze liczb od 1 do 'x':
 - Co druga liczba ma w rozkładzie na czynniki pierwsze 2^1
 - Co czwarta liczba ma w rozkładzie na czynniki pierwsze 2^2 ( jedna dwójka bierze się z podzielności przez 2, a druga z podzielności przez 4 )
 - Co ósma liczba ma w rozkładzie na czynniki pierwsze 2^3 ( jedna dwójka bierze się z podzielności przez 2, druga z podzielności przez 4, a trzecia z podzielności przez 8 ). I tak dalej...
Oznacza to, że co 2 mamy dodatkową dwójkę, oprócz tego co cztery mamy dodatkową dwójkę,  co osiem i tak dalej.
Czyli jeśli podzielimy 'x' przez każdą potegę dwójki mniejszą lub równą 'x' i zsumujemy wyniki to dowiemy się ile w rozkładach na czynniki jest dwójek. 
Dokładnie tak samo robimy dla 5 i w ten sposób wiemy ile jest 5 i 2 w rozkładach, dołączając to co napisałem wcześniej mamy rozwiązanie

Zaraz wkleję rozwiązanie (najpierw polecam spróbować samemu =) ): LINK_JUZ_NIE_DZIALA
Proszę o zadawanie pytań, jeśli opisałem coś niejasno