Сколько нулей в конце числа?

[Ward]

Добрый день форумчане!
Помогите решить задачку. Сколькими нулями оканчивается число $100!=1\cdot 2\cdot 3 \dots\cdot 100$?

[Whitaker]

Для этого Вам надо найти с каким показателем входит $2$ и $5$ в разложении $100!$ на простые множители.
Надеюсь Вы знаете формулу

[Ward]

Как узнать степени двойки и пятерки?
Число 100! ведь огромное.. как его разложить на множители?

[svv]

Ward писал(а):

Число 100! ведь огромное.. как его разложить на множители?

Да, Вы правы, число это огромное.

Но я Вам помогу. Я сейчас проделаю львиную долю работы по разложению 100! на множители. Смотрите:
$100!=1\cdot 2\cdot 3 \dots\cdot 100$

[Whitaker]

Не надо ничего разлагать.
Просто используйте следующий факт:
Показатель, с которым простое число $p$ входит в произведение $n!$, равен

$$\Big[\frac{n}{p}\Big]+\Big[\frac{n}{p^2}\Big]+\Big[\frac{n}{p^3}\Big]+\cdots$$

[Ward]

svv ну да верно, а что это дает?
Whitaker откуда эта формула?

[apriv]

Не надо ничего разлагать.
Просто используйте следующий факт:
Число $100!$ оканчивается ровно на двадцать четыре нуля.

-- 03.08.2012, 18:31 --

Ward в сообщении #602782 писал(а):

svv ну да верно, а что это дает?

Возьмите и посчитайте, сколько среди этих чисел содержат $5$ в качестве простого сомножителя, и сколько раз.

[Whitaker]

apriv в сообщении #602784 писал(а):

Не надо ничего разлагать.
Просто используйте следующий факт:
Число $100!$ оканчивается ровно на двадцать четыре нуля.

Это Вам очевидно, но ТС это врядли понятно, но уверен, что он поймет это сейчас.

[svv]

apriv в сообщении #602784 писал(а):

Не надо ничего разлагать.
Просто используйте следующий факт:
Число $100!$ оканчивается ровно на двадцать четыре нуля.

apriv, я оценил.

[Aritaborian]

apriv в сообщении #602784 писал(а):

Просто используйте следующий факт

Ага. Решение задачи: «Используем тот факт, что $100!$ заканчивается на 24 нуля. Ответ: 24» ;-D

[apriv]

Whitaker в сообщении #602787 писал(а):

Это Вам очевидно, но ТС это врядли понятно, но уверен, что он поймет это сейчас.

Ровно это же можно сказать и про Ваш «факт» про показатель $p$ в разложении $n!$.

[Ward]

Whitaker
число $5$ входит с показателем $\Big[\frac{100}{5}\Big]+\Big[\frac{100}{5^2}\Big]=20+4=24$, а 2 с показателм $\Big[\frac{100}{2}\Big]+\Big[\frac{100}{2^2}\Big]+\cdots=97$

[Whitaker]

apriv в сообщении #602792 писал(а):

Whitaker в сообщении #602787 писал(а):

Это Вам очевидно, но ТС это врядли понятно, но уверен, что он поймет это сейчас.

Ровно это же можно сказать и про Ваш «факт» про показатель $p$ в разложении $n!$.

Пожалуй соглашусь с Вами... беру свои слова обратно!
Ward ну да что-то подобное должно выйти. Теперь Вам понятно почему число 100! оканчивается 24 нулями?

[Sonic86]

Ward в сообщении #602782 писал(а):

Whitaker откуда эта формула?

Попробуйте ее вывести сами, это несложно. Сначала простые вопросы:
Какова степень двойки в числе $k!$ при $k<p$?
Какова степень двойки в числе $p!$?
Какова степень двойки в числе $(2p)!$?
Какова степень двойки в числе $(p^2)!$?
Для вывода можно использовать такой факт: если $v_p(x)$ - степень числа $p$ в числе $x$, то $v_p(ab)=v_p(a)+v_p(b)$.

[svv]

Попробую и я.
Мы перемножаем числа:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,...
Каждое второе число в этом списке (2,4,6,8,10,12,14,16...) делится на 2, то есть содержит по крайней мере одну двойку в своем разложении на простые множители.
Каждое четвертое число (4,8,12,16,...) делится на 4, то есть содержит по крайней мере две двойки в своем разложении на простые множители.
Каждое восьмое число (8,16,24,32...) делится на 8, то есть содержит по крайней мере три двойки в своем разложении на простые множители.
И так далее. Вот так и можно пересчитать все двойки. И аналогично пятерки.