e-olymp
Məsələlər

Факториал

Факториал

Факториалом натурального числа N (обозначается N!) называется произведение всех натуральных чисел от 1 до N включительно: N! = 1×2×3××N.

Требуется определить, каким количеством цифр "0" заканчивается запись числа N! в K-ичной системе счисления.

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

Во входном файле содержится два числа: NиK(1N109, 2K5000).Оба числа записаны в десятичной системе счисления.

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

В выходной файл вывести количество нулей, которыми в K-ичной системе счисления оканчивается число N!. Число вывести в десятичной системе счисления.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
Sample 1
10000  10

Sample 2
10000  2

Sample 3
123456789  4800

Sample 4
27110307  4107
Çıxış verilənləri
Sample 1
2499

Sample 2
9995

Sample 3
15432096

Sample 4
376531