Как я могу посчитать количество конечных нулей факториала числа в определенной системе счисления?
Давайте рассмотрим случай, когда мы находимся в 10-й системе счисления, а затем посмотрим, как мы можем обобщить это в универсальное решение. Нам дано число N и для его факториала нужно найти количество конечных нулей. Решение будет довольно простым — сумма:
Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ...
Её мы можем обобщить в такую формулу:
Почему в примере выше мы делим на 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.
Проделываем тоже самое с 3:
Рассмотрим еще один пример.
Пусть число N = 16, система счисления B = 16. Факториал 16! = 20922789888000, а 20922789888000 в 16-ой системе — 130777758000. Мы видим, что в конечной системе счисления факториал исходного числа имеет три ноля. При разложении 16 на простые множители, получим 2, 2, 2, 2. Здесь у нас только одно уникальное число, поэтому пункт 2 выполняется только один раз:
P.S. Большую часть материала для поста перевел отсюда. Автор — Aditya Ramesh.