CS
Задачник Базовый курс EN

Задача

Фибоначчи по модулю

теория чисел матрица разделяй и властвуй

Числа Фибоначчи: F₀ = 0, F₁ = 1, Fn = Fn−1 + Fn−2. Найдите остаток от деления Fn на m — для n вплоть до 10¹⁸, когда само число Фибоначчи содержит больше двухсот квадриллионов цифр.

Вход

В первой строке число запросов q (1 ≤ q ≤ 10 000). В каждой из следующих строк — n и m (0 ≤ n ≤ 10¹⁸, 1 ≤ m ≤ 10⁹).

Выход

Для каждого запроса — Fn mod m в отдельной строке.

Примеры

Пример 1

Вход
6
0 10
1 10
2 10
10 1000
50 1000000007
90 1000000000
Выход
0
1
1
55
586268941
370816120

Ограничения

Время · Python
5000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
4 теста

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Шаг рекуррентности переводит пару (Fn, Fn−1) в пару (Fn+1, Fn), и делает это линейно. Как записать линейное преобразование пары чисел?

2Идея

Матрицей: (Fn+1, Fn) = [[1, 1], [1, 0]] · (Fn, Fn−1). Значит, n шагов — это n-я степень матрицы, а степень считается быстрым возведением за log₂ n умножений матриц. Получается [[1, 1], [1, 0]]n = [[Fn+1, Fn], [Fn, Fn−1]].

3Разбор

Тот же цикл, что для чисел, только умножение — матричное 2×2, и остаток берётся у каждого элемента. Начальный «ответ» — единичная матрица. При m = 1 все остатки — нули, поэтому единичную матрицу аккуратно записывают как (1 mod m): иначе для n = 0 ответ выйдет 1 вместо 0.

В Go при m ≤ 10⁹ каждое произведение меньше 10¹⁸, а сумма двух — меньше 2·10¹⁸: uint64 хватает. Для модулей около 10¹⁸ уже не хватило бы.

3+Решение
4Сложность

60 возведений матрицы в квадрат и не больше 60 домножений, каждое — 8 умножений чисел: около тысячи операций на запрос вместо 10¹⁸.

5Типичные ошибки
  • Цикл по рекуррентности. 10¹⁸ итераций — тридцать лет даже на быстром языке.
  • Остаток только в конце. Числа Фибоначчи растут экспоненциально: без остатка после каждого умножения Python будет считать с гигантскими числами, а Go переполнится уже к F₉₄.
  • m = 1. Единичная матрица 1 mod 1 — нулевая, и ответ на любой запрос — 0.

Алгоритмы задачи

NUM Алгоритм Быстрое возведение в степень aⁿ за O(log n) умножений: квадраты по битам показателя. O(log n) умножений 2 задачи NUM Алгоритм Матрицы и рекуррентности Степень матрицы: пути длины k в графе, линейные рекуррентности, матрица переноса и цепи Маркова. O(m³ log k) для A^k размера m × m 2 задачи
Каталог алгоритмов