Информатика • 11 класс

Задачи длинной арифметики. Многоразрядные целые числа (Python)

Стандартные типы данных Python позволяют работать с очень большими числами, однако принцип длинной арифметики можно реализовать вручную. Для этого число разбивается на ячейки фиксированного размера.
Принцип работы: число разбивается на ячейки фиксированного размера. В примере ниже используется основание 1 000 000 — каждая ячейка хранит до 6 цифр. Это позволяет эффективно умножать, складывать и выводить большие числа без потери точности.

Пример. Подсчитать факториал 100 (100!).

N = 33
d = 1000000
mas = [0] * (N + 1)
mas [0] = 1
for j in range(2, 101):
	k = 0
	for i in range (N + 1):
		s = mas [i] * j + k
		mas [i] = s % d
		k = s // d
		first = True
		for i in range (N, -1, -1):
			if mas [i] != 0 or not first:
			if first:
				print (mas [i], end="")
				first = False
			else:
				print (f"{mas [i]:06d}", end="")

Было полезно?