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

[Xenia1996]

Обычно я пользуюсь следующим алгоритмом, до которого, кстати, сама докопалась.

Число n двоек в разложении числа $m!$ на простые множители равно $[\frac{m}{2}]+[\frac{m}{4}]+[\frac{m}{8}]+\dots +[\frac{m}{2^k}]+\dots$
Например, в числе $2011!$ будет

$[\frac{2011}{2}]+[\frac{2011}{4}]+[\frac{2011}{8}]+\dots +[\frac{2011}{2^k}]+\dots=2002$

двойки.

При этом n, как правило, не намного отличается от m.

А как сосчитать быстрее? Для $2011!$ данный алгоритм ещё более-менее приемлем, а как, скажем, быть с $(2011!)!$? Есть какая-то формула?

[ИСН]

В теории сложности алгоритмов, как проедешь первые определения, на обочине стоит серый могильный камень с надписью:
"Он пытался получить ответ быстрее, чем можно его записать".

[Xenia1996]

ИСН в сообщении #430669 писал(а):

В теории сложности алгоритмов, как проедешь первые определения, на обочине стоит серый могильный камень с надписью:
"Он пытался получить ответ быстрее, чем можно его записать".

Если Вы о Колмогоровской сложности, то это не так. Скажем, бесконечную последовательность 1010101010... может породить программа, которую даже я смогу написать, хотя программировать не умею

[ИСН]

Нет, это другое. Я о той сложности, которая фигурирует в "P=NP".

[Xenia1996]

ИСН в сообщении #430675 писал(а):

Нет, это другое. Я о той сложности, которая фигурирует в "P=NP".

Дык, вроде ж до сих пор открытая проблема?

[ИСН]

Проблему я упомянул только как указатель того, из какой это области.

[Xenia1996]

ИСН в сообщении #430678 писал(а):

Проблему я упомянул только как указатель того, из какой это области.

Давайте сформулируем вопрос по-другому.
На олимпиаде меня спрашивают, сколько двоек в разложении $2011!$? Я тупо беру листочек и считаю. Теперь мне задают такой же вопрос об очень большом числе и я могу лишь ответить, что число двоек приблизительно равно самому числу. А как точно посчитать?

[ИСН]

Ответ сам представляет собой очень большое число, которое даже записать быстро не получится (т.е. даже если уже его знаешь). Это возвращает нас к моему первому замечанию.

[Vince Diesel]

Для $m=2^k$ число двоек равно $n=2^k-1$. А в общем случае разность $m-n$ равна количеству единиц в двоичной записи числа $m$.

[bot]

Xenia1996 в сообщении #430680 писал(а):

На олимпиаде меня спрашивают ...

Возможно они хотят услышать тождество $\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor$?
C его помощью каждое слагаемое суммы получается делением предыдущего с округлением вниз.

[Xenia1996]

Vince Diesel в сообщении #430702 писал(а):

Для $m=2^k$ число двоек равно $n=2^k-1$. А в общем случае разность $m-n$ равна количеству единиц в двоичной записи числа $m$.

Спасибо!

В принципе, то же самое, ибо количество единичных битов мы считаем по такому же алгоритму, каждый раз делим пополам и берём целую часть. Только там складывать не надо, просто писать единичку, если не делится пополам, и 0, если делится.

-- Вс апр 03, 2011 12:48:55 --

bot в сообщении #430708 писал(а):

Xenia1996 в сообщении #430680 писал(а):

На олимпиаде меня спрашивают ...

Возможно они хотят услышать тождество $\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor$?
C его помощью каждое слагаемое суммы получается делением предыдущего с округлением вниз.

(Оффтоп)

В любом случае, правильный ответ они обязаны засчитать.