Problem Introduction
The Fibonacci numbers are defined as follows: \(F_0=0\), \(F_1=1\),and \(F_i=F_{i-1}+F_{i-2}\) for $ i \geq 2$.
Problem Description
Task.Given two integers \(n\) and \(m\), output \(F_n \ mod \ m\)(that is, the remainder of \(F_n\) when divided by \(m\)).
Input Format.The input consists of two integers \(n\) and \(m\) given on the same line(separated by a space).
Constraints. \(1 \leq n \leq 10^{18}, 2 \leq m \leq 10^5\).
Output Format.Output \(F_n \ mod \ m\)
Sample 1.
Input:
281621358815590 30524
Output:
11963
Solution
# Uses python3
import sys
def get_fibonaccihuge(n, m):
x, y = 0, 1
pisano = []
while True:
pisano.append(x)
x, y = y % m, (x+y) % m
if x == 0 and y == 1:
break
return pisano[n % len(pisano)]
if __name__ == '__main__':
input = sys.stdin.read()
n, m = map(int, input.split())
print(get_fibonaccihuge(n, m))