Question

факториалом числа n (обозначается n!) называется произведение от 1 до n (1*2*3...*n). Как найти, на сколько нулей заканчивается число

Answer 1

Число оканчивается на k нулей = число k раз делится на 10 = число k (не меньше k) раз делится на 2 и на 5 = в разложении числа на простые делители (основная теорема арифметики) содержится k (не меньше) двоек и пятерок.

В случае с n!, нужно посчитать, сколько (и с какой кратностью) чисел от 1 до n делятся на 5 (соответственно, сколько пятерок будет в разложении). Количество двоек можно не считать, т.к. очевидно, их будет не меньше пятерок.

Количество чисел от 1 до n, которые делятся на 5, равно n div 5 (n поделить на 5 нацело).

Заметим, что числа, которые делятся на 25, делятся на 5 дважды, т.е. и учитывать их нужно дважды. Один раз мы их посчитали в n div 5, так что нужно включить их еще раз - всего их n div 25.

Соответственно, числа, которые делятся на 125, делятся на 5 трижды, так что нужно прибавить еще n div 125, и т.д.

Т.е. результат:

= (n div 5) + (n div 25) + (n div 125) + (n div 625) + ...

Суммирование продолжается до тех пор, пока соответствующая степень 5 не превысит n.

Пример: n = 100

100! = 93 326 215 443 944 152 681 699 238 856 266 700 490 715 968 264 381 621 468 592 963 895 217 599 993 229 915 608 941 463 976 156 518 286 253 697 920 827 223 758 251 185 210 916 864 000 000 000 000 000 000 000 000

- 24 нуля

(100 div 5) + (100 div 25) = 20 + 4 = 24

Answer 2

Пусть дано число n, при этом $1leq frac{n}{5^{k}}<5$, при некотором k∈N; Тогда число нулей в десятичной записи числа n равно $[frac{n}{5^{k}}]+[frac{n}{5^{k-1}}]+...+[frac{n}{5}]$, где [x] - целая часть числа x.