Примитивная задача на формулу Лежандра, кой я нарешал достаточно в своем профиле
(можете посмотреть, там и более сложные формулировки есть).
Формула Лежандра помогает определять вхождение простого в факториал, а произведение последовательных натуральных чисел и есть факториал, то есть:
![1*2*3*4*5...*10 = 10!](https://tex.z-dn.net/?f=+1%2A2%2A3%2A4%2A5...%2A10+%3D+10%21+)
и произносится, как десять факториал.
К самой сути, как же определить кол-во людей в том или ином факториале? - Все просто, достаточно посчитать сколько в это произведение входит простой множитель 5, почему 5? - Потому что с произведением с 2 он дает тот заветный 0, который мы и пытаемся найти. Для примера 5^2*2^2 = 100, т.е. 5^2 два нуля. Есть ещё некая зависимость от двойки, но двойка в факториале встречается чаще 5-ки, поэтому достаточно найти лишь вхождение 5.
Формула простая:
![n!, [n//5]+[n//5^2]+[n//5^3]\ldots[n//5^k], k \in \mathbb{N}](https://tex.z-dn.net/?f=+n%21%2C+%5Bn%2F%2F5%5D%2B%5Bn%2F%2F5%5E2%5D%2B%5Bn%2F%2F5%5E3%5D%5Cldots%5Bn%2F%2F5%5Ek%5D%2C+k+%5Cin+%5Cmathbb%7BN%7D+)
,
(// - целочисленное деление)
очевидно, что начиная с определенного слагаемого они будут равны 0 и цепочка прервется.
Посчитаем для нашего примера:
![25, [25//5]+[25//25]+[25/125]\ldots[25/5^k]](https://tex.z-dn.net/?f=+25%2C+%5B25%2F%2F5%5D%2B%5B25%2F%2F25%5D%2B%5B25%2F125%5D%5Cldots%5B25%2F5%5Ek%5D+)
, после k>2, слагаемые равны 0, поэтому получаем
Тем самым в
![<span> \prod\limits_{n=1}^{25} n](https://tex.z-dn.net/?f=%C2%A0%3Cspan%3E%C2%A0%5Cprod%5Climits_%7Bn%3D1%7D%5E%7B25%7D+n+%C2%A0)
- 6 нулей.