Как максимально оптимизировать код Python?

Question

[God_of_Gods]

from math import factorial
N, base = map(int,input().split())

NN = factorial(N)
def d(n, b):
    d.t = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    r=''
    while n:
        n, y = divmod(n, b)
        r=d.t[y]+r
    return r

f = str(d(NN, base)[::-1])
a = len(f)
p = 0
for i in f:
    if i == '0':
        p += 1
    else:
        break
print(p)

код не проходит тесты по времени, помогите оптимизировать)

Comments

[Wataru]

Можно полный текс задачи? Вы, похоже, считаете количество нулей в записи факториала в заданной системе счисления? Я правильно понял?

[God_of_Gods]

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

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

входные данные

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

Исходные данные

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

[U235U235]

Не надо считать сам факториал. Считайте сколько встречается двоек-пятерок и чисел заканчивающихся на нули.

[U235U235]

U235U235, это для десятичной системы. Для любой другой есть свои двойки-пятерки и круглые числа.

[God_of_Gods]

U235U235, Не очень понял как это заменит факториал
Мы же ведь потом переводим его в другую систему
и там 0 считаем

[o5a]

God_of_Gods, что такое 0 ? это произведение 2 на 5 (или сам 0). Сколько бы ни умножали другие числа (1..9), последний 0 не получится. Это для десятичной системы. Для другой системы соответственно свои множители, дающие 0.

[U235U235]

o5a, совершенно верно, для других систем счисления будут свои множители, предлагаю их вам найти. А также подсчитать числа заканчивающиеся на ноль (аналог для десятичной системы 10-1 ноль, 20 -1 ноль 100-2 нуля, 110 - 1 ноль, 1000 -3 нуля и т.д.)

Answer 1

[Wataru]

Проблема не в коде, а в алгоритме. Долго строить всю строку и считать в ней нули.

Есть вот такая формула. Для каждого простого числа можно опредерить степень просто деля n (не факториал!) на это простое число нацело, пока не получится 0 и суммировать все результаты.

Но это работет только для простых чисел. Т.е. чтобы узнать, в какой степени число 10 входит в N! (или сколько нулей на конце в деситичной записи) надо узнать, сколько раз 2 и 5 входят в N! и взять минимум.

Т.е. надо разложить k на простые множители, для каждого простого множителя подсчитать, сколько раз он входит в n! по формле выше. Потом поделить это на степень простого числа в k, и по всем делителям k взять минимум.