e-olymp 123. Количество нулей у факториала

by

7

Задача

Найти количество нулей в конце записи факториала числа $n$.

Входные данные

Одно число $n$ $(1 \leqslant n \leqslant2\cdot10^9)$

Выходные данные

Количество нулей в конце записи $n!$

Тесты

№ ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 1 0
 2 7 1
 3 12 2
 4 100 24
 5 306 75
 6 5000 1249

Код

Решение

Каждый нуль в конце искомого числа возникает от произведения чисел 2 и 5 — других вариантов нет. Очевидно, множителей 5 будет меньше множителей 2. Значит, количество нулей определяется исключительно количеством множителей-пятерок. Один такой множитель содержат числа 5, 10, 15, 20, 25, …, $n$ — всего их насчитывается $\frac{n}{5}$. Два множителя содержат числа 25, 50, …, $n$ всего их $\frac{n}{5^2}$.Три множителя содержат $\frac{n}{5^3}$.Складывая количество множителей с учетом их повторения, найдем общее их количество:

$\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\ldots+\lfloor\frac{n}{5^k}\rfloor$

Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.

Ссылки

Формула разложения на простые множители

Условие задачи на e-olymp

Код на Ideone

Засчитанное решение на e-olymp 

 

Related Images:

7 thoughts on “e-olymp 123. Количество нулей у факториала”

    • В математике не принято обозначать умножение точкой. Нужен или крестик, или точка, или ничего.
    • Поработайте, пожалуйста над текстом. Он не согласован. Есть повторы и «то» без «если».
    • Пожалуйста, сделайте отступы в коде.
    • Если делаете пустую строку в коде, будьте готовы объяснить зачем.
    • Если берете формулу в скобки, то не так $$(\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\dots+\lfloor\frac{n}{5^k}\rfloor),$$ а так $$\left(\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\dots+\lfloor\frac{n}{5^k}\rfloor\right).$$Но зачем вообще это делать?
    • Не нужно использовать буквы кириллицы в адресе публикации — это создает проблемы при экспорте и генерирует длинные не читаемые ссылки.

  2. Поскольку Вам не удалось исправить полностью замечания, напишу детальнее.

    • В математике не принято обозначать умножение точкой. Нужен или крестик, или точка, или ничего. В Вашем случае пишут так $2\cdot10^9.$
    • Поработайте, пожалуйста над текстом. Сделайте осмысленным выражения — «в составе факториала число имеет 10», «количество десяток в факториале». Или просто удалите два первых предложения. Обязательно объясните как именно Вы получили формулу для нахождения числа делителей равных пяти в произведении первых $n$ натуральных чисел.
    • Пожалуйста, сделайте отступы в коде. О том как и зачем их делать можно прочесть здесь.
    • «воспользоватся разложение»? Либо «воспользоватся разложением», либо «использовать разложение».
    • Но, в любом случае, нужно объяснить подробнее, что Вы имеете в виду. Пока Вы всё еще не объяснили откуда взялась эта волшебная формула и как ее получить воспользовавшись «разложением на простые числа». Я даже не знаю, что это за разложение. Знаю разложение на простые сомножители. Это оно? Кстати, это был не риторический вопрос. Я ожидаю, что Вы ответите на него в комментариях.
    • Небольшая подсказка. Мне кажется, что Вы не сможете объяснить формулу не сказав, что $n!$ это произведение всех натуральных чисел не превышающих $n.$ Но тут Вам виднее.

  4. Я использовал разложение на простые числа, которая укзанна в статье о факториалах в википедии. Как я понял данная формулировка не верна. Я планнирую заменить «разложение на просыте числа» на формулу Лежандра.

    • Владислав, я просил добавить объяснение формулы и вы с этим успешно справились. Молодец.
    • Ещё я просил дать ссылку на то место откуда Вы эту формулу взяли. Но вы этого не сделали. Чтобы Вам было легче я эту ссылку даже привел в своем прошлом комментарии. Уверен, вам удастся сделать это в своем пояснении.
    • И ещё — почему в статье вы отступы сделали, а код по ссылкам так и остался кашей? Это нужно исправить.

  6. Хорошо. Я засчитываю работу, но напишу еще несколько слов. Возможно это поможет в дальнейшем. Капитан Врунгель в мультике пел «В море синем, как в аптеке, всё имеет суть и вес». Всё имеет суть и вес не только в море синем, а и… везде. Хорошая и ценная вещь иногда отличается от плохой и малоценной всего лишь некоторыми деталями — тут чуть косо, там чуть криво- вот и не шедевр. Будьте внимательны к деталям. Они должны иметь смысл.
    По Вашей работе. Не буду писать о деталях, чтобы Вы не сочли это за придирки, но посмотрите на свою ссылку на e-olymp. Это правильные отступы?

Добавить комментарий