No.526 Find the N-th Term of the Fibonacci Sequence Modulo M
タグ : / 解いたユーザー数 700
作問者 :
Leonardone
/ テスター :
くれちー
Problem Statement
Find the remainder when the $N$-th term of the Fibonacci sequence is divided by $M$.
(Beginners should be careful about overflow and the remainder calculation.)
The $1$-st term of the Fibonacci sequence is $0$, and the $2$-nd term is $1$.
Examples and the definition (recurrence relation) of the Fibonacci sequence are shown below.
$F_{1} = 0$
$F_{2} = 1$
$F_{3} = F_{3 - 1} + F_{3 - 2} = F_{2} + F_{1} = 1 + 0 = 1$
$F_{4} = F_{4 - 1} + F_{4 - 2} = F_{3} + F_{2} = 1 + 1 = 2$
…
$F_{N} = F_{N - 1} + F_{N - 2}$
* Fibonacci number - Wikipedia* Fibonacci numbers - The On-Line Encyclopedia of Integer Sequences (OEIS)
Input
N M
$N$ and $M$ are given separated by a single-byte space.
$10 \le N \le 5000000 = 5 * 10^{6}$
$2 \le M \lt 2^{31}$
Output
Output the remainder when the $N$-th term of the Fibonacci sequence is divided by $M$. Print a newline at the end.
Sample
Sample 1
Input
10 20
Output
14
Since $N = 10, M = 20$, we compute the remainder when the $10$-th term of the Fibonacci sequence is divided by $20$.
We have $F_{1} = 0, F_{2} = 1, F_{3} = 1, F_{4} = 2, F_{5} = 3, F_{6} = 5, F_{7} = 8, F_{8} = 13, F_{9} = 21, F_{10} = 34$, so dividing by $20$ gives a remainder of $14$.
Sample 2
Input
20 1000
Output
181
Sample 3
Input
30 17
Output
13
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。