No.526 フィボナッチ数列の第N項をMで割った余りを求める

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 154
作問者 : LeonardoneLeonardone / テスター : クレチークレチー

0 ProblemId : 1344 / 出題時の順位表

問題文

フィボナッチ数列の第$N$項を$M$で割った余りを求めてください。
(初心者の方は、オーバーフローと余りの計算に注意してください)

フィボナッチ数列の第$1$項を$0$、第$2$項を$1$とします。
フィボナッチ数列の例と定義(漸化式)を示します。

$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}$
フィボナッチ数 - Wikipedia
フィボナッチ数列 - オンライン整数列大辞典(OEIS)

入力

N M

$N$と$M$が半角スペース区切りで与えられます。
$10 \le N \le 5000000 = 5 * 10^{6}$
$2 \le M \lt 2^{31}$

出力

フィボナッチ数列の第$N$項を$M$で割った余りを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
10 20
出力
14

$N = 10, M = 20$なのでフィボナッチ数列の第$10$項を$20$で割った余りを計算します
$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$となるので$20$で割ると余りは$14$になります

サンプル2
入力
20 1000
出力
181

サンプル3
入力
30 17
出力
13

提出ページヘ