У меня ребенок учится на курсах Сириус (Алгоритмы на Python) и там дали эту задачу. Для решения построили визуализацию последней цифры на графике в Excel. Наглядно видно, где что и как повторяется. На чем повторение "сбивается" выносим в отдельный ряд, и т.п. пока не начнет повторяться все. Дальше ребенок решил сам. Сначала он написал код, а потом уже сделал описание.
1. Факториал делится на ряды:
1 * 2 * 3... * 9 * 11 * 12 * 13 ... * 19 * 21...
*10 * 20 * 30.. 90 * 110 * 120... *190 * 210...
*100 * 200 * 300.. 900 * 1100 * 1200... *1900 * 2100...
*1000 * 2000 * 3000.. 9000 * 11000 * 12000... *19000 * 21000...
*10000 * 20000 * 30000.. 90000 * 110000 * 120000... *190000 * 210000...
....
2. Расчет для ряда 1 * 2 * 3 ... :
2.1. Если заданное число меньше чем 2, результат 1.
2.2. Разделим полученый ряд на два ряда. Первый ряд состоит из чисел оканчивающихся на 2 и 5, второй из всех остальных чисел.
2.2.1 Первый ряд: 2 * 5 * 12 * 15 * 22 * 25 * 32 * 35 *...
2.2.2 Второй ряд: 1 * 3 * 4 * 6 * 7 * 8 * 9 * 11 * 13 * 14 * 16 * 17 * 18...21 * 23...94 * 96...
2.3 Сначала мы считаем последнюю цифру для второго ряда.
Начиная с 4, последняя цифра будет повторятся каждые 28 умножений (40 если прибавить кол-во пропущенных чисел - ряд из п. 2.2.1, а также ряды 10..., 100... из п. 1). Для определения цифры получим остаток от деления заданного числа на 40.
2.4. Считаем последнюю цифру для первого ряда (2.2.1)
разбиваем ряд на пары (2*5) * (12*15) * (22*25) * ...
Число 2, 12, 22, 32... можно записать как x2 аналогично и с 5, 15, 25, 35... (x5) . Сделаем преобразование
x2 * x5 = x2/2*2 * x5/5*5 = x2/2 * (2*5) * x5/5 = (x2/2) * 10 * (x5/5)
при умножении на десять последняя ненулевая цифра не поменяется. Поэтому достаточно рассчитать (x2/2) * (x5/5).
2.5. Рассчитаем x2/2. Числа 2, 12, 22, 32 ... при делении на 2 оканчиваются цифрами 1, 6, 1, 6, 1, 6, ... . Что не влияет на результат. Так как у второго ряда (п 2.2.2) в ответе четное число, а умножение четного числа на 6 и 1 даeт число с той же цифрой на конце.
2.5.1 Заметим, что каждое второе число, оканчивающеся на 6 будет с четной цифрой перед 6: 6, 26, 46 ... Таких чисел будет 1/40 от общего числа множителей.
2.6. Рассчитаем x5/5. Числа 5, 15, 25, 35 ... при делении на 5 оканчиваются цифрами 1, 3, 5, 7:
a1, b3, c5, d7, e9, f1, g3, h5, i7, j9, k1, l3... что уже меняет результат.
2.6.1. Сгруппируем их по последней цифре:
(1 * 11 * 21...) * (3 * 13 * 23 * 33...) * (5 * 15 * 15 * ... ) * ....
2.6.2. Если перемножать числа оканчивающиеся на 1 (первая скобка) то последняя цифра будет повторяться так: 1, 1, 1 на результат не повлияет, поэтому единицы не считаем.
Если перемножать числа оканчивающиеся на 3 то последняя цифра будет повторяться так: 3,9,7,1 (период 4).
Если перемножать числа оканчивающиеся на 7 то последняя цифра будет повторяться так: 7,9,3,1 (период 4)
Если перемножать числа оканчивающиеся на 9 то последняя цифра будет повторяться так: 9,1 (период 2)
Для определения итога достаточно получить остаток от деления количества таких чисел на период.
2.6.3. Чисел, оканчивающихся на 5 (3я скобка в п. 2.6.1) будет 1/50 от общего числа множителей. Обозначим их a5, b5, c5 ... и сделаем преобразование:
a5 * b5 * c5 * ... = (a5 / 5 * 5) * (b5 / 5 * 5) * (c5 / 5 * 5) *...= (a5 /5 * b5 /5 * c5/5 * d5/5 *) ... * (5 * 5 * 5 * 5 * ...) =
2.6.4. Каждую свободную пятёрку из этого выражения (последняя скобка (5 * 5 * 5...)) умножим на число x6 (которое образовалось в п. 2.5.1 и которое не учитывалось ранее. Причем в этом числе перед "6" четная цифра). Такое произведение оканчивается цифрой 3. (Пятерок (1/50) не больше, чем шестерок (1/40)). Итог по всей скобке вычисляется аналогично 2.6.2.
2.6.5. У первой скобки 2.6.3 (a5 /5 * b5 /5 * c5/5 * d5/5 * ...) последние цифры будут тоже повторятся 1, 3, 5, 7, 9... и расчет выполняется аналогично 2.6. Общее число пятерок (см. п. 2.6.4) в итоге будет 1/50 + 1/250 + 1/1250 + .. .от общего числа множителей, что не больше, чем шестерок (1/40, п. 2.6.1).
2.7. Если заданное число оканчивается на цифру между 2 и 4 (включительно). Это означает что в ряду 2.2.1 есть непарная x2. Полученый ответ умножаем на два.
3. Расчет для остальных рядов из п. 1 аналогичен, т.к. последние нули на результат не влияют и их можно просто отбросить.
4. После расчетов для всех рядов (п. 1) перемножаем результаты.
5. Так как расчет расчет рядов (п. 1) не зависит друг от друга, то программу можно сделать многопроцесорной.
Сложность алгоритма. В программе 2 цикла - внешний (по рядам п. 1) и внутренний - по степеням 5 (п. 2.6), оба зависят от log(n). Таким образом, для небольших чисел O(log(n)^2). Небольшие - это для которых сложность арифметических операций O(1). Такое число в исходном вопросе.
Начиная с версии 3 в Python целые числа имеют неограниченную разрядность. Арифметические операции с большими целыми числами имеют сложность O(log(n)), таким образом для больших чисел сложность алгоритма O(log(n)^3).
На курсах Сириус ограничения: число до 10^8 и время до 2 сек. Привиденный ниже код (многопроцессорный вариант) на i7-12700 (8P + 4E ядер, 20 потоков) за 2 сек рассчитывает числа до 10^2400 (Python 3.12.4 Win64).
Код для Python 3 под спойлерами
Однопроцессорный вариант
# Last non-zero decimal digit of factorial
# Single processor version
# Code by Vasilii Belousov, 5th grade
# Engineering and Technical School named after P.R.Popovich,
# Moscow, Russia
b = []
v = {}
def init():
global b
global v
m = 3
for i in range(4, 44) :
r = i % 10
if r in (0, 2, 5):
b.append(m)
continue
m *= i
m = m % 10
b.append(m)
v = {3: [3,9,7,1],7:[7,9,3,1],9:[9,1]}
def ost(a):
if a > 3 :
c = (a-4)%40
c = b[c]
else:
if a<3:
c=1
else:
c=3
ad = a%10
if ad >1 and ad<5:
c*= 2
return c
def enddigit(a,ch):
g = a//10
if a%10 >= 5:
g +=1
c=0
posle = ch//2
while g > posle :
v = g//5
if g%5 > posle:
v +=1
c += v
if g%5 >= 3:
g+=5
g = g//5
return c
def pnnc(ch,colvo):
c = v[ch][colvo%len(v[ch])-1]
return c
def dlya5(a):
c1 = enddigit(a,3)
co = 1
for v in range(5,10,2):
c2 = enddigit(a,v)
if v == 5:
c2+=c1
v = 3
c = pnnc(v,c2)
co = (co *c)%10
return co
def main():
a = int(input())
init()
c = 1
while a >1:
c = c * ost(a)*dlya5(a)%10
a = a//10
print(c)
main()
Многопроцессорный вариант
# Last non-zero decimal digit of factorial
# Multiprocessing version
# Code by Vasilii Belousov, 5th grade
# Engineering and Technical School named after P.R.Popovich,
# Moscow, Russia
from multiprocessing import Pool
def ost(a):
b = (2, 2, 2, 4, 2, 8, 8, 8, 8, 4, 6, 6, 6, 2, 6, 4, 4, 4, 4, 2, 8, 8, 8, 6, 8, 2, 2, 2, 2, 6, 4, 4, 4, 8, 4, 6, 6, 6, 6, 8)
if a > 3 :
c = (a-4)%40
c = b[c]
else:
if a<3:
c=1
else:
c=3
ad = a%10
if ad >1 and ad<5:
c*= 2
return c
def generator_c(a):
while a>1:
yield a
a = a//10
return
def enddigit(a,ch):
g = a//10
if a%10 >= 5:
g +=1
c=0
posle = ch//2
while g > posle :
v = g//5
if g%5 > posle:
v +=1
c += v
if g%5 >= 3:
g+=5
g = g//5
return c
def pnnc(ch,colvo):
v = {3: [3,9,7,1],7:[7,9,3,1],9:[9,1]}
c = v[ch][colvo%len(v[ch])-1]
return c
def dlya5(a):
c1 = enddigit(a,3)
co = 1
for v in range(5,10,2):
c2 = enddigit(a,v)
if v == 5:
c2+=c1
v = 3
c = pnnc(v,c2)
co = (co *c)%10
return co
def f(x):
return ost(x)*dlya5(x)
def main():
a = int(input())
p = Pool()
c=1
for x in p.imap_unordered(f,generator_c(a)):
c = c*x%10
print(c)
if __name__ == '__main__':
main()
Средний
Простой
