CS
Задачник Базовый курс EN

Задача

Нулевые ячейки факториала

теория чисел разложение на множители массив

Длинное число хранится как массив «цифр» по большому основанию b, младшая первой: в Python b = 2³⁰, в олимпиадных программах часто 10⁹ или 10⁴. В статье о длинной арифметике видно, что у 1000! первые 33 ячейки по основанию 2³⁰ — нули: это нули на конце числа, записанного по основанию 2³⁰. По основанию 10⁹ таких ячеек 27, а в обычной десятичной записи у 1000! на конце 249 нулей.

Сколько нулевых младших ячеек у n! по основанию b? Иначе говоря, сколькими нулями оканчивается запись n! в системе счисления с основанием b. Сам факториал вычислять не нужно — и не получится: n доходит до 10¹⁸.

Вход

В первой строке число запросов t (1 ≤ t ≤ 100). В каждой из следующих — два целых n и b (1 ≤ n ≤ 10¹⁸, 2 ≤ b ≤ 10¹²).

Выход

Для каждого запроса — число нулей на конце записи n! по основанию b.

Примеры

Пример 1

Вход
4
1000 1073741824
1000 1000000000
1000 10
10 10
Выход
33
27
249
2

Ограничения

Время · Python
6000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
7 тестов

Разбор

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

1Подсказка 1

Запись числа по основанию b оканчивается k нулями ровно тогда, когда число делится на bk. Для b = 10 это известная задача: нулей столько, сколько пятёрок в разложении n!. Почему пятёрок, а не двоек?

2Подсказка 2

Сколько раз простое p входит в n!? Каждое кратное p среди чисел 1…n даёт по одному множителю, каждое кратное p² — ещё по одному, кратное p³ — ещё. А если b = 2¹⁰·3, что кончится раньше — двойки или тройки?

3Идея

Разложим b = p₁a₁·…·pmam. Пусть простое pi входит в n! с показателем vi — по формуле Лежандра v = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + … Тогда bk делит n!, пока k·ai ≤ vi для всех i, и ответ — min ⌊vi/ai⌋.

4Разбор

Раскладываем b пробным делением на простые до 10⁶ (их заранее даёт решето): если после этого что-то осталось, это простое больше миллиона — у числа до 10¹² не может быть двух таких множителей. Для каждого простого считаем показатель Лежандра: складываем ⌊n/p⌋, ⌊n/p²⌋, … В Go удобнее делить n на p снова и снова, чем возводить p в степени: так не будет переполнения при n около 10¹⁸.

Почему формула Лежандра верна: среди чисел 1…n ровно ⌊n/p^j⌋ делятся на pj. Число, в котором p входит в степени e, посчитано в слагаемых j = 1, …, e — по разу в каждом, то есть ровно e раз.

Для 1000! по основанию 2³⁰: двойка входит 500 + 250 + 125 + … = 994 раза, и ⌊994/30⌋ = 33 нулевые ячейки. По основанию 10⁹ = 2⁹·5⁹: пятёрок 249, двоек 994, ответ min(⌊994/9⌋, ⌊249/9⌋) = 27. А у Go и V8, где основание 2⁶⁴, нулевых слов было бы ⌊994/64⌋ = 15.

4+Решение
5Сложность

Разложение b — до 78 498 пробных делений; показатель Лежандра — O(logp n) делений для каждого простого. На запрос — O(π(10⁶) + log n).

6Типичные ошибки
  • «Кончается самое большое простое». Для 10 это так, но не всегда: у 100! по основанию 3072 = 2¹⁰·3 двоек 97, троек 48, и нулей ⌊97/10⌋ = 9, а не 48.
  • Забытый показатель. По основанию 12 = 2²·3 двойки расходуются парами: v₂ нужно делить на 2.
  • Переполнение. pj при n ≈ 10¹⁸ и большом p выходит за 64 бита, если сначала умножать, а потом сравнивать.

Алгоритмы задачи

NUM Алгоритм Длинная арифметика Числа длиннее машинного слова: цифры по основанию 10⁹ или 2³⁰, переносы, столбик и дорогая печать. сложение O(n), умножение и деление столбиком O(n²), печать в десятичной записи O(n²) или O(M(n) log n) 2 задачи NUM Алгоритм Решето Эратосфена Все простые до n за O(n log log n): вычёркиваем кратные каждого простого, начиная с его квадрата. O(n log log n) 2 задачи
Каталог алгоритмов