Как я могу посчитать количество конечных нулей факториала числа в определенной системе счисления?
Давайте рассмотрим случай, когда мы находимся в 10-й системе счисления, а затем посмотрим, как мы можем обобщить это в универсальное решение. Нам дано число N и для него нужно найти количество конечных нулей. Решение будет довольно простым — сумма:
Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ...Её мы можем обобщить в такую формулу:
$$display$$sumlimits_{i=1}^infty {N over 5^i}.$$display$$
Почему 5? Это просто. Конечный ноль получается только тогда, когда в составе факториала число имеет 10. Таким образом, посчитав количество десяток в факториале, мы узнаем количество конечных нулей.
Почему в примере выше мы делим на 5? Потому что 10 может быть получено умножением 5 на 2. Поэтому полное решение будет иметь две формулы:
$$display$$sumlimits_{i=1}^infty {N over 5^i}$$display$$
и
$$display$$sumlimits_{i=1}^infty {N over 2^i}.$$display$$
Но, рассуждая логически, мы знаем, что первая сумма будет меньше, поэтому нам нужно посчитать только её (подробнее можно почитать тут).
Решение нашей проблемы
Для подсчёта конечных нулей факториала числа в определенной системе счисления я составил алгоритм, приведенный ниже:
- Разложить число B системы счисления на простые множители.
- Разделить число N на каждый уникальной простой множитель K, домножая K сам на себя до тех пор, пока $inline$N over K$inline$ будет больше единицы, при этом округляя каждый результат до меньшего целого.
- Если при разложении числа системы счисления мы получили несколько одинаковых простых множителей K, то результат выше мы должны разделить на количество одинаковых K.
- Из всех делений N на каждый уникальный множитель K выбрать наименьшее частное, которое и будет нашим ответом.
Я покажу это на примере.
Пусть число N = 5, система счисления B = 12. Факториал 5! = 120, а 120 в 12-ой системе — A0. Мы видим, что в конечной системе счисления факториал исходного числа имеет один ноль. При разложении 12 на простые множители, получим 2, 2, 3. У нас есть два уникальных числа: 2 и 3. Следуя нашему алгоритму выполним пункт 2 с числом 2.
$$display$${5 over 2 } + {5 over 4 } + {5 over 8 } + ... = 2+1+0+... =3.$$display$$
Но двойка встречалась дважды при разложении 12-и, поэтому конечный результат мы делим на 2 и округляем до меньшего целого. В результате получаем 1.
Проделываем тоже самое с 3:
$$display$${5 over 3 } + {5 over 9 } + ... = 1+0+... =1.$$display$$
Таким образом, мы получили два частных от делений числа N на простые множители числа системы счисления. Они оба равны 1, поэтому меньшее нам выбирать не приходится и мы просто даем ответ — 1.
Рассмотрим еще один пример.
Пусть число N = 16, система счисления B = 16. Факториал 16! = 20922789888000, а 20922789888000 в 16-ой системе — 130777758000. Мы видим, что в конечной системе счисления факториал исходного числа имеет три ноля. При разложении 16 на простые множители, получим 2, 2, 2, 2. Здесь у нас только одно уникальное число, поэтому пункт 2 выполняется только один раз:
$$display$${16 over 2 } + {16 over 4 } + {16 over 8 } + {16 over 16 } + {16 over 32 } + ... = 8+4+2+1+0+... =15.$$display$$
При разложении у нас было четыре двойки, поэтому сумму делений делим на 4 с округлением до меньшего целого: $inline$ {15over 4} = 3.$inline$
P.S. Большую часть материала для поста перевел отсюда. Автор — Aditya Ramesh.
Автор: ra44o
