Как я могу посчитать количество конечных нулей факториала числа в определенной системе счисления?
Давайте рассмотрим случай, когда мы находимся в 10-й системе счисления, а затем посмотрим, как мы можем обобщить это в универсальное решение. Нам дано число N и для его факториала нужно найти количество конечных нулей. Решение будет довольно простым — сумма:
Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ...
Её мы можем обобщить в такую формулу: Почему 5? Это просто. Конечный ноль получается только тогда, когда в составе факториала число имеет 10. Таким образом, посчитав количество десяток в факториале, мы узнаем количество конечных нулей.
Почему в примере выше мы делим на 5? Потому что 10 может быть получено умножением 5 на 2. Поэтому полное решение будет иметь две формулы: и Но, рассуждая логически, мы знаем, что первая сумма будет меньше, поэтому нам нужно посчитать только её (подробнее можно почитать тут).
Решение нашей проблемы
Для подсчёта конечных нулей факториала числа в определенной системе счисления я составил алгоритм, приведенный ниже:
- Разложить число B системы счисления на простые множители.
- Разделить число N на каждый уникальной простой множитель K, домножая K сам на себя до тех пор, пока будет больше единицы, при этом округляя каждый результат до меньшего целого.
- Если при разложении числа системы счисления мы получили несколько одинаковых простых множителей K, то результат выше мы должны разделить на количество одинаковых K.
- Из всех делений N на каждый уникальный множитель K выбрать наименьшее частное, которое и будет нашим ответом.
Я покажу это на примере.
Пусть число N = 5, система счисления B = 12. Факториал 5! = 120, а 120 в 12-ой системе — A0. Мы видим, что в конечной системе счисления факториал исходного числа имеет один ноль. При разложении 12 на простые множители получим 2, 2, 3. У нас есть два уникальных числа: 2 и 3. Следуя нашему алгоритму выполним пункт 2 с числом 2.
Но двойка встречалась дважды при разложении 12-и, поэтому конечный результат мы делим на 2 и округляем до меньшего целого. В результате получаем 1.
Проделываем тоже самое с 3:
Таким образом, мы получили два частных от делений числа N на простые множители числа системы счисления. Они оба равны 1, поэтому меньшее нам выбирать не приходится и мы просто даем ответ — 1.
Рассмотрим еще один пример.
Пусть число N = 16, система счисления B = 16. Факториал 16! = 20922789888000, а 20922789888000 в 16-ой системе — 130777758000. Мы видим, что в конечной системе счисления факториал исходного числа имеет три ноля. При разложении 16 на простые множители, получим 2, 2, 2, 2. Здесь у нас только одно уникальное число, поэтому пункт 2 выполняется только один раз:
При разложении у нас было четыре двойки, поэтому сумму делений делим на 4 с округлением до меньшего целого:
P.S. Большую часть материала для поста перевел отсюда. Автор — Aditya Ramesh.
Комментарии (14)
yurrig
18.03.2019 01:14Ваша первая формула говорит, что в конце числа 25 имеется 6 нулей.
ra44o Автор
18.03.2019 01:20В конце факториала 25, вы имеете в виду?
yurrig
18.03.2019 01:32Нам дано число N и для него нужно найти количество конечных нулей. Решение будет довольно простым — сумма:
Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ...
Подставляем N = 25 и…
Формула действительно для оконечных нулей не N, а N! Виноват, не сообразил сразу, что просто N! выпало.WellD
18.03.2019 12:36Ведь всё правильно вы прочли, «Нам дано число N и для него нужно найти количество конечных нулей» нужно читать «Нам дано число N и для его факториала нужно найти количество конечных нулей».
Было бы хорошо, чтобы в текст статьи внесли такую правку.
Sirion
18.03.2019 08:25Помнится, я эту формулу выводил на математических сборах в девятом классе. Полчаса ушло. Причём это была не сама задача, формула применялась для решения основной задачи. В общем, немного мелковато для статьи.
saluev
18.03.2019 11:02+1В песочнице лежит целая статья про циклический сдвиг, так что тут всё ещё не так плохо.
Sirion
18.03.2019 11:27Не могу оспорить ваше утверждение. А вы читаете песочницу? Мужественный человек.
dkokarev
18.03.2019 19:04+1Эта задача встречалось совсем недавно codeforces.com/contest/1114/problem/C
nzeemin
А зачем мне считать количество конечных нулей факториала числа в определенной системе счисления?
Sdima1357
Ну кому-то нужно число пи с триллионами знаков( а его даже прочитать за всю жизнь не успеешь), а вот автору число нулей в факториалах. Почему бы и нет? Зато в отличии от вычисления числа пи, энтропия вселенной почти не меняется, и счета за энергию небольшие.
ra44o Автор
У меня недавно была такая задача. Пример решения я нашел на сайте, который указал в конце поста. Аналогов на русском я не нашел, поэтому решил перевести.
Возможно, вам это никогда и не понадобится. Я писал этот пост для людей, которые столкнутся с такой задачей.