Рус Uzb Eng

C32A. Marslik faktoriallar
Ограничение по времени: 2 cекунды
Ограничение по памяти: 64 мегабайт

В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно K различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.
Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием K. А символы в конце – это конечно же нули – ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули начиная с 5!=1*2*3*4*5=120. А у числа 100! в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 – так что у предположения профессора есть разумные основания!
Теперь ученым срочно нужна программа, которая по заданным числам N и K найдет количество нулей в конце записи в системе счисления с основанием K числа N!=1*2*3*...*(N-1)*N, чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!

Входные данные:
На первой строке входного файла находятся числа N и K, разделенные пробелом. (1 <= N <= 109, 1 <= K <= 1000).

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

Пример ввода Пример вывода
5 10
1 2
100 10
1
0
24
Область:
Источник задачи:

Отправить решение на проверку

Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.