Calculate Fibonacci n-th term modulo m
Fibonacci sequence is defined by obtaining each next term in the sequence by adding up the previous two, while the first two elements are 0 and 1:
Given the number
n, you are asked to calculate the
n-th Fibonacci numbers modulo
As we’re only interested in the result modulo
m, the value of
ncan be very large.
The only line of the input contains two integers
n(0 ≤ n ≤ ) and
m(1 ≤ m ≤ 50).
The program should print the result of
- fib(0) = 0 ⇒ 0 mod 5 = 0
- fib(1) = 1 ⇒ 1 mod 5 = 1
- fib(6) = 8 ⇒ 8 mod 5 = 3
As we’re calculating the fibonacci numbers modulo
m, and the next number always depends on the previous two, the numbers start to repeat at some point. You can try printing many values modulo
mand notice the pattern after which they start repeating.
As the numbers start repeating at some point, you can directly calculate the
n-th Fibonacci number instead of looping through all of them.
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB