Задача на ТЧ(теорию чисел), хочется код или хотя бы алгоритм по решению данной задачи.
Дано два числа n, m.
нужно узнать сколько нулей будет на конце у n! в m-ой системе счисления.
Например, при n = 5 и m = 10, ответ будет 1(5! = 120(в десятичной системе) - 1 ноль)
при n = 5 и m = 2, ответ будет 0(5! = 101(в двоичной системе) - 0 нолей)
n <= 1000000000
2 <= k <= 1000
второй тест неверен, там ответ 3
1111000
Ты ошибаешься: 5! = 120₁₀ = 1111000₂ -> ответ 3.
Раскладываем m на простые множители p[i] и считаем, сколько раз каждый множитель входит в m - q[i].
Вычисляем, сколько раз каждый p[i] в ходит в n!: t[i] = n / p[i] + n / p[i]² + n / p[i]³ + ...
Вычисляем s[i] = t[i] / q[i].
Находим min(s[i]) - это и будет кол-во нулей.
Например, у нас n = 50, m = 45.
45 = 3 * 3 * 5
p = {3, 5}
q = {2, 1}
t = {50 / 3 + 50 / 9 + 50 / 27, 50 / 5 + 50 / 25} = {16 + 5 + 1, 10 + 2} = {32, 12}
s = {32 / 2, 12 / 1} = {16, 12}
min(16, 12) = 12
Ответ: 12 нулей. Количество нулей в конце числа X в M-ной системе счисления это максимальное число k при котором X делится на M^k без остатка.
Стало быть надо найти такое максимальное k для N!. Может не самый быстрый, но код будет таким
n = int(input())
m = int(input())
result = 0
fact_n = 1
for i in range(1, n+1):
____fact_n *= i
while fact_n % m == 0:
____result += 1
____fact_n //= m
print(result)
Ответьте в комментариях если не прав
upd: вы добавили ограничения. С такими ограничениями нужен алгоритм по-эффективнее