Марсианские факториалы

Задачу протестировать можно тут.

(Время: 1 сек. Память: 16 Мб)

В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно K различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.

Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием K. А символы в конце – это конечно же нули – ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули начиная с 5! = 1·2·3·4·5 = 120. А у числа 100! в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 – так что у предположения профессора есть разумные основания!

Теперь ученым срочно нужна программа, которая по заданным числам N и K найдет количество нулей в конце записи в системе счисления с основанием K числа N! = 1·2·3·…·(N-1)·N, чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!

Входные данные

Входной файл INPUT.TXT содержит числа N и K, разделенные пробелом. (1 ≤ N ≤ 10^9, 2 ≤ K ≤ 1000).

Выходные данные

Выведите в выходной файл OUTPUT.TXT число X - количество нулей в конце записи числа N! в системе счисления с основанием K.

Примеры

№ INPUT.TXT OUTPUT.TXT

1 5 10 1

2 100 10 24

3 100 6 48

4 3 10 0

Для начала необходимо разобраться откуда берутся нули в конце числа N в разных системах счисления, так как мы будем рассматривать разложение на простые множители, факториал будем считать каким-то числом N.

Теперь разберемся с десятичной системой счисления, пускай какое-то число N имеет вид:

Очевидно, что нули в конце числа будут появляться только при умножение 2 на 5, то есть количество нулей можно выразить как min(a1, a2), видим что a1 всегда будет больше a2, в итоге получим что количество нулей в числе N в десятичной системе счисления равно min(a1, a2) = a2.

Научимся считать на конкретном примере.

Пускай мы хотим узнать сколько нулей содержит 130!.

Посчитаем сначала количество пятёрок в 130!, для этого 130 разделим на 5, потом есть числа где пятёрки встречаются два раза, поэтому разделим 130 на 25, потом 130 на 125 и так далее пока это возможно. Просуммировав получим количество пятёрок - 26 + 5 + 1 = 32. То есть 130! содержит 32 нуля.

По этому принципу мы можем подсчитать сколько содержится число p в некотором числе N!.

Пускай мы работает в системе счисления с основанием K, разложим K на простые множители, так же мы имеем разложение N. Тогда нулей будет столько сколько разложение числа K встречается в разложение N.

Теперь выведем обобщенный принцип подсчета. Находим какие простые множители содержит в себе число K, запоминаем сколько встречается каждый множитель. Потом для каждого простого множителя из K считаем количество таких простых чисел в N!, делим это количество на число раз, которые этот множитель входит в K, и выбираем минимум из ответа или этого результата.

Разберем на конкретном примере.

Например, найдем количество нулей в числе 50! в системе счисления с основанием 12.

12 = 3 * 2^2

Найдем количество 3 в 50!: 50 / 3 + 50 / 9 + 50 / 27 = 22

3 входит в разложение K в первой степени, тогда текущий ответ: 22 / 1 = 22

Найдем количество 2 в 50!: 50 / 2 + 50 / 4 + 50 / 8 + 50 / 16 + 50 / 32 = 47

2 входит в разложение K во второй степени, тогда текущий ответ

min(22, 47 / 2) = min(22, 23) = 22

И того имеем 22 нуля в 50! в системе счисления с основанием 12.

Теперь рассмотрим детали реализации:

В строке 4 выбираем достаточно большое число (ответ не должен превысить его). В строке 5 цикл который идет по простым делителям k (благодаря тому что мы делим k внутри цикла на текущие простое число). В строках 8-11 считаем сколько раз число k содержит простой делитель i, и в тоже время делим его на этот делитель. В строках 14-17 считаем сколько раз число n! содержит простой делитель i. В строке 18 выбираем минимальное число между ответов и текущим полученным результатом.

Спасибо за внимание.