Даны целые числа \(1 \leq n \leq 10^{18}\) и \(2 \leq m \leq 10^5\), необходимо найти остаток от деления n-го числа Фибоначчи на m.
Решение
Последовательность остатков при делении чисел Фибоначчи на натуральное число периодична. Период Пизано - это длина периода этой последовательности.
Для нахождения остатка от деления n-го числа Фибоначчи на натуральное число m достаточно найти все числа периода Пизано для данного m, затем найти остаток от деления n на длину периода, и взять число из периода Пизано под этим номером.
Саму последовательность Фибоначчи можно не вычислять, для нахождения периода использовать только остатки.
Первые числа в периоде Пизано - 0 и 1. Длина периода не больше m * 6 (доказательство этого не нашёл).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
n, m = [int(x) for x in input().split()] def find_pisano(n, m): pisano = [] pisano.append(0) # при делении на 1 остаток будет всегда 0 if m == 1: return pisano pisano.append(1) # при m > 0 остатки от деления первого и второго числа Фибоначчи # всегда 0 и 1 if n <= 1: return pisano n0 = 0 n1 = 1 for __ in range(m * 6): # для ускорения не вычисляем числа Фибоначчи полностью # берём только остатки по модулю m n0, n1 = n1, (n0 + n1) % m pisano.append(n1 % m) # Проверяем не начался ли новый период # период всегда начинается с 0 и 1 if pisano[len(pisano) - 1] == 1 \ and pisano[len(pisano) - 2] == 0: break return pisano[:-2] pisano = find_pisano(n, m) print(pisano) print(pisano[n % len(pisano)]) |
Что означает строчка:
for __ in range(m * 6): ?
Цикл выполняется m*6 раз. Длина периода не может быть больше m*6, поэтому ограничиваем цикл.