Эффективный алгоритм для вычисления самой правой ненулевой цифры факториала числа в Python
Эффективно вычислить самую правую ненулевую цифру n факториала
Я хочу вычислить самую правую цифру факториала заданного числа и распечатать ее. Что я сделал до сих пор:
import math
n = int(input())
fact = math.factorial(n)
print(str(fact).rstrip('0')[-1])
но я все еще получаю ограничения по времени и ищу более быстрые решения.
Стоит отметить, что для решения этой проблемы я должен использовать python.
Также отмечу, что n от 1 до 65536, ограничение по времени 0,5 секунды и у меня 256 мегабайт памяти.
Насколько большой из n вы, как ожидается, сможете справиться? Когда я пробую этот подход для n=100000, я могу получить ответ через несколько секунд. «но я все еще получаю ограничения по времени» — означает ли это, что вы предоставляете код чьей-то тестовой программе, например онлайн-тестеру? В этом случае убедитесь, что вы понимаете, как должны работать ввод и вывод. Может случиться так, что input будет ждать вечно, потому что тестер не предоставит ввод на стандартный ввод и может не принять что-то, что printed, как действительный вывод. Проверьте, должны ли вы, например. вместо этого читайте или записывайте файлы.
@MrSmith42 MrSmith42 Сначала я тоже так думал, но очевидные попытки обойти это не ускоряют мои тесты.
@Карл Кнехтель; Хорошо, я вижу, что вычисление факториала - неправильный подход, поскольку нам никогда не нужен номер дырки).
@KarlKnechtel Я думаю, вы пытались сделать неправильные очевидные вещи? :-) Или вы пробовали с n, не похожим на их сейчас упомянутый лимит?
Подход @KellyBundy OP уже занимает всего 1,25 секунды для n = 65536 на моей машине, а моя машина довольно старая. Я не думаю, что ответ Сеона вообще очевиден.
@KarlKnechtel Я имел в виду не Сеона, а тот, где я вычисляю полный факториал, как в вопросе, но избегаю строки, как сказал MrSmith42 (что делает его намного быстрее). Первый здесь.
Ах, этот первый подход, безусловно, лучше, чем, например. повторение с divmod.
Ответы 3
Существует изящная рекурсивная формула, которую вы можете использовать: пусть D(n) будет последней ненулевой цифрой в n!
- Если n<10, используйте справочную таблицу
- Если предпоследняя цифра n нечетная, D(n) = 4 * D(n//5) * D(единичная цифра n)
- Если предпоследняя цифра n четная, D(n) = 6 * D(n//5) * D(единичная цифра n)
См. этот пост на бирже математического стека для доказательства.
Переводим в код:
def last_nonzero_factorial_digit(n):
lookup = [1, 1, 2, 6, 4, 2, 2, 4, 2, 8]
if n < 10:
return lookup[n]
if ((n // 10) % 10) % 2 == 0:
return (6 * last_nonzero_factorial_digit(n // 5) * lookup[n % 10]) % 10
else:
return (4 * last_nonzero_factorial_digit(n // 5) * lookup[n % 10]) % 10
На моем ноутбуке эта версия работает примерно в 14 000 раз быстрее с 5-значным числом.
Большое спасибо, код сработал отлично.
Простой достаточно быстрый, просто вычислите факториал, а затем удалите столько нулей, сколько раз встречается простой множитель 5 (поскольку это то, что вызывает нули вместе с более частым простым множителем 2). Каждое пятое число от 1 до n дает один простой множитель 5, каждое пятое из них дает еще один и т. д.
def Kelly(n):
res = math.factorial(n)
while n:
n //= 5
res //= 10**n
return res % 10
Сравните с вашим пределом n = 65 536:
0.108791 seconds just_factorial
1.434466 seconds Shayan_original
0.553055 seconds Shayan_answer
0.000016 seconds Seon
0.208012 seconds Kelly
0.029500 seconds Kelly2
Мы видим, что простое вычисление факториала без извлечения нужной цифры достаточно быстро. Просто ваше исходное извлечение цифры через строку происходит медленно.
(Примечание: OP Shayan сказал, что решение их ответа «работает для меня и выполняет свою работу», а мое решение быстрее, в основном поэтому я сказал, что мое решение достаточно быстрое (также потому, что для меня оно намного меньше 0,5 с). Похоже, они только удалили их, потому что они не могли этого объяснить.)
Еще один простой и быстрый способ:
def Kelly2(n):
prod = 1
twos = 0
for i in range(2, n + 1):
while not i % 2:
i //= 2
twos += 1
while not i % 5:
i //= 5
twos -= 1
prod = prod * i % 10
return prod * pow(2, twos, 10) % 10
Здесь мы сами умножаем числа от 1 до n. Но извлеките простые множители 2 и 5 и посчитайте их отдельно. Тогда н! = 2twos * 5fives * Произведение приведенных факторов. Поскольку пары 2 и 5 вызывают нежелательные конечные нули, вместо этого подсчитайте, сколько двоек у нас есть, которые мы не можем соединить с пятерками. Это то, что делает мой код. Тогда nFactorialWithoutTrailingZeros = 2twos * ProductOfReducedFactors. И мы получаем его последнюю цифру с помощью % 10, которую мы можем использовать на протяжении всего расчета, чтобы уменьшить размер ProductOfReducedFactors.
Тестовый код (Попробуйте онлайн!):
import math
from time import time
def just_factorial(n):
math.factorial(n)
return -1
def Shayan_original(n):
fact = math.factorial(n)
return str(fact).rstrip('0')[-1]
def Shayan_answer(n):
a = n // 5
b = n - 5 * a
fact_a = math.factorial(a)
fact_b = math.factorial(b)
power_a = 2 ** a
res = fact_a * fact_b * power_a
while (res % 10 == 0):
res //= 10
return int(res % 10)
def Seon(n):
lookup = [1, 1, 2, 6, 4, 2, 2, 4, 2, 8]
if n < 10:
return lookup[n]
if ((n // 10) % 10) % 2 == 0:
return (6 * Seon(n // 5) * lookup[n % 10]) % 10
else:
return (4 * Seon(n // 5) * lookup[n % 10]) % 10
def Kelly(n):
res = math.factorial(n)
while n:
n //= 5
res //= 10**n
return res % 10
def Kelly2(n):
prod = 1
twos = 0
for i in range(2, n + 1):
while not i % 2:
i //= 2
twos += 1
while not i % 5:
i //= 5
twos -= 1
prod = prod * i % 10
return prod * pow(2, twos, 10) % 10
funcs = just_factorial, Shayan_original, Shayan_answer, Seon, Kelly, Kelly2
# Correctness
for n in *range(1001), 65536:
expect = funcs[1](n)
for f in funcs[2:]:
result = str(f(n))
assert result == expect
# Speed
for f in funcs:
t = time()
f(65536)
print(f'{time() - t :8.6f} seconds ', f.__name__)
Решение, основанное на вашем ответе (просто повторяя ваш шаг сокращения), его оптимизированная версия, которая превосходит решение Сеона, и оптимизированная версия решения Сеона. Время для n = 65 536:
2.04 ± 0.03 μs Seon_optimized
2.54 ± 0.04 μs Kelly3_optimized
4.18 ± 0.04 μs Seon
20.51 ± 0.09 μs Kelly3
Код (Попробуйте онлайн!):
def Kelly3(n):
res = 1
while n:
res *= factorial(n % 5)
n //= 5
res <<= n
return res % 10
def Kelly3_optimized(n):
res = 1
twos = 0
while n:
res *= (1, 1, 2, 6, 24)[n % 5]
n //= 5
twos += n
shift = twos and (twos % 4 or 4)
return (res << shift) % 10
def Seon_optimized(n):
lookup = 1, 1, 2, 6, 4, 2, 2, 4, 2, 8
Lookup = 6, 6, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2
res = 1
while n >= 10:
res *= Lookup[n % 20]
n //= 5
return res * lookup[n] % 10
def Seon(n):
lookup = [1, 1, 2, 6, 4, 2, 2, 4, 2, 8]
if n < 10:
return lookup[n]
if ((n // 10) % 10) % 2 == 0:
return (6 * Seon(n // 5) * lookup[n % 10]) % 10
else:
return (4 * Seon(n // 5) * lookup[n % 10]) % 10
from timeit import timeit
from statistics import mean, stdev
from math import factorial
funcs = Seon, Kelly3, Kelly3_optimized, Seon_optimized
# Correctness
for n in *range(10001), 65536:
expect = str(funcs[0](n))
for f in funcs[1:]:
result = str(f(n))
assert result == expect
# Speed
times = {f: [] for f in funcs}
def stats(f):
ts = [t * 1e6 for t in sorted(times[f])[:100]]
return f'{mean(ts):6.2f} ± {stdev(ts):4.2f} μs '
for _ in range(1000):
for f in funcs:
t = timeit(lambda: f(65536), number=1)
times[f].append(t)
for f in sorted(funcs, key=stats):
print(stats(f), f.__name__)
1-й. Я бы не стал создавать String.