Как быстрее сосчитать число двоек в разложении факториала?

Если записать множители факториала в десятичном и двоичном виде, то можно легко увидеть, сколько каждый множитель добавляет двоек в результат. Например, множители 18!:
$01|00001$
$02|00010$
$03|00011$
$04|00100$
$05|00101$
$06|00110$
$07|00111$
$08|01000$
$09|01001$
$10|01010$
$11|01011$
$12|01100$
$12|01101$
$14|01110$
$15|01111$
$16|10000$
$17|10001$
$18|10010$
...

Таким образом, по одной двойке добавляют множители 2, 6, 10, 14, 18, по две - 4, 12, по три - 8, по четыре - 16. Итого 16 двоек. Просматривается зависимость:
$1 \cdot round(\frac{18}{4}) + 2 \cdot round(\frac{18}{8}) + 3 \cdot round(\frac{18}{16}) + 4 \cdot round(\frac{18}{32})$. Или в общем виде:
$\sum_{i=1}^{\infty} i \cdot round(\frac{m}{2^{i+1}})$, где $m - основание факториала$.
Сложность вашего алгоритма $O(m)$, а этого $O(log_2 m)$



Редактировалось 1 раз(а). Последний 03.04.2011 20:34.

Цитата
museum
Оценивая сложность своего алгоритма г. Hlopchik учитывал сложность записи всех чисел от 1 до m в двоичной системе?

Нет, количество слагаемых, если развернуть знак суммы. Если формулу реализовать на какой-нибудь машине, то количество простых шагов, чтобы получить решение, будет равно $\log m \cdot С$, где С - некоторая константа



Редактировалось 1 раз(а). Последний 04.04.2011 00:37.