Вычислить n-й член последовательности Фибоначчи по модулю m
Последовательность Фибоначчи определяется так, что каждое новое число получается путём сложения двух предыдущих, причём первые два элемента равны 0 и 1:
Задано число
n. Необходимо вычислить n-е число Фибоначчи по модулю m.Так как нам нужен только результат по модулю
m, значение n может быть очень большим.Входные данные
В единственной строке находятся два целых числа
n (0 ≤ n ≤ ) и m (1 ≤ m ≤ 50).Выходные данные
Программа должна вывести результат вычисления .
Примеры
Вход | Выход |
0 5 | 0 |
1 5 | 1 |
6 5 | 3 |
Пояснение
- fib(0) = 0 ⇒ 0 mod 5 = 0
- fib(1) = 1 ⇒ 1 mod 5 = 1
- fib(6) = 8 ⇒ 8 mod 5 = 3
Hint 1
Поскольку мы вычисляем числа Фибоначчи по модулю
m, и каждое следующее число зависит от двух предыдущих, в каком-то месте значения начинают повторяться. Можно попробовать вывести много чисел по модулю m и заметить закономерность повторений.Hint 2
Когда значения начинают повторяться, можно напрямую определить
n-е число Фибоначчи, не вычисляя все числа подряд.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB