[Из песочницы] Подсчет конечных нулей факториала числа в любой системе счисления18.03.2019 04:47

Как я могу посчитать количество конечных нулей факториала числа в определенной системе счисления?


Давайте рассмотрим случай, когда мы находимся в 10-й системе счисления, а затем посмотрим, как мы можем обобщить это в универсальное решение. Нам дано число N и для него нужно найти количество конечных нулей. Решение будет довольно простым — сумма: 

Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ...


Её мы можем обобщить в такую формулу:

$\sum\limits_{i=1}^\infty {N \over 5^i}.$

Почему 5? Это просто. Конечный ноль получается только тогда, когда в составе факториала число имеет 10. Таким образом, посчитав количество десяток в факториале, мы узнаем количество конечных нулей.
Почему в примере выше мы делим на 5? Потому что 10 может быть получено умножением 5 на 2. Поэтому полное решение будет иметь две формулы:

$\sum\limits_{i=1}^\infty {N \over 5^i}$

и 

$\sum\limits_{i=1}^\infty {N \over 2^i}.$

Но, рассуждая логически, мы знаем, что первая сумма будет меньше, поэтому нам нужно посчитать только её (подробнее можно почитать тут).

Решение нашей проблемы


Для подсчёта конечных нулей факториала числа в определенной системе счисления я составил алгоритм, приведенный ниже:

  1. Разложить число B системы счисления на простые множители.
  2. Разделить число N на каждый уникальной простой множитель K, домножая K сам на себя до тех пор, пока $N \over K$ будет больше единицы, при этом округляя каждый результат до меньшего целого.
  3. Если при разложении числа системы счисления мы получили несколько одинаковых простых множителей K, то результат выше мы должны разделить на количество одинаковых K.
  4. Из всех делений N на каждый уникальный множитель K выбрать наименьшее частное, которое и будет нашим ответом.


Я покажу это на примере.
Пусть число N = 5, система счисления B = 12. Факториал 5! = 120, а 120 в 12-ой системе — A0. Мы видим, что в конечной системе счисления факториал исходного числа имеет один ноль. При разложении 12 на простые множители получим 2, 2, 3. У нас есть два уникальных числа: 2 и 3. Следуя нашему алгоритму выполним пункт 2 с числом 2.

${5 \over 2 } + {5 \over 4 } + {5 \over 8 } + ... = 2+1+0+... =3.$

Но двойка встречалась дважды при разложении 12-и, поэтому конечный результат мы делим на 2 и округляем до меньшего целого. В результате получаем 1.

Проделываем тоже самое с 3:

${5 \over 3 } + {5 \over 9 } + ... = 1+0+... =1.$

Таким образом, мы получили два частных от делений числа N на простые множители числа системы счисления. Они оба равны 1, поэтому меньшее нам выбирать не приходится и мы просто даем ответ — 1.

Рассмотрим еще один пример.

Пусть число N = 16, система счисления B = 16. Факториал 16! = 20922789888000, а 20922789888000 в 16-ой системе — 130777758000. Мы видим, что в конечной системе счисления факториал исходного числа имеет три ноля. При разложении 16 на простые множители, получим 2, 2, 2, 2. Здесь у нас только одно уникальное число, поэтому пункт 2 выполняется только один раз:

${16 \over 2 } + {16 \over 4 } + {16 \over 8 } + {16 \over 16 } + {16 \over 32 } + ... = 8+4+2+1+0+... =15.$

При разложении у нас было четыре двойки, поэтому сумму делений делим на 4 с округлением до меньшего целого: $ {15\over 4} = 3.$

P.S. Большую часть материала для поста перевел отсюда. Автор — Aditya Ramesh.

© Habrahabr.ru