Проект Эйлера - Задача 160

Question

Для любого N пусть f (N) будет последними пятью цифры перед конечными нулями в N !. Например,

9!  = 362880 so f(9)=36288 
10! = 3628800 so f(10)=36288 
20! = 2432902008176640000 so f(20)=17664

Найти f (1 000 000 000 000)

Я успешно решил этот вопрос для приведенных примеров, моя функция может правильно найти f (9), f (10) и т. Д. Однако она борется с большими числами, особенно с числом, которое задает проблема - f (10) ^ 12).

Мои текущие оптимизации следующие: я удаляю конечные нули из множителя и суммы и сокращаю сумму до 5 цифр после каждого умножения. Код на Python выглядит следующим образом:

def SFTR (n):
 sum, a = 1, 2
 while a < n+1:
  mul  = int(re.sub("0+$","",str(a)))
  sum *= mul
  sum  = int(re.sub("0+$","",str(sum))[-5:])
  a   += 1
 return sum 

Может кто-нибудь сказать мне, почему эта функция масштабируется так сильно и почему она занимает так много времени. Кроме того, если кто-нибудь может намекнуть мне в правильном направлении, чтобы оптимизировать мой алгоритм. (достаточно названия общей темы) Спасибо.

Обновление:

Я внес некоторые изменения в оптимизацию, и она значительно быстрее, но все еще недостаточно быстра для f (10 ^ 12). Может кто-нибудь сказать мне, что делает мой код медленным или как сделать его быстрее?

def SFTR (n):
    sum, a = 1, 2
    while a < n+1:
        mul  = a

        while(mul % 10 == 0): mul = mul/10
        mul  = mul % 100000

        sum *= mul

        while(sum % 10 == 0): sum = sum/10
        sum  = sum % 100000

        a   += 1
    return sum

Answer 1

mul может стать очень большим. Это необходимо? Если бы я попросил вас вычислить последние 5 ненулевых цифр 1278348572934847283948561278387487189900038 * 38758 от руки , сколько именно цифр первого числа вам действительно нужно знать?

Answer 2

Построение строк часто стоит дорого. Я бы предпочел использовать оператор по модулю при усечении до пяти последних цифр.

python -m timeit 'x = str(111111111111111111111111111111111)[-5:]'
1000000 loops, best of 3: 1.09 usec per loop
python -m timeit 'x = 111111111111111111111111111111111 % 100000'
1000000 loops, best of 3: 0.277 usec per loop

То же самое относится и к удалению конечных нулей. Должен быть более эффективный способ сделать это, и вам, вероятно, не нужно делать это на каждом этапе.

Я не проверял ваш алгоритм на корректность, но это всего лишь подсказка для оптимизации.

Answer 3

На самом деле, вы можете даже заметить, что существует только ограниченный набор возможных конечных ненулевых цифр. Если я правильно помню, есть только несколько тысяч возможных последовательных ненулевых комбинаций цифр, когда вы смотрите только последние 5 цифр. Например, возможно ли, чтобы последняя ненулевая цифра была нечетной? (Здесь игнорируются особые случаи 0! И 1!)