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

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 650
作問者 :

Leonardone / テスター :

くれちー

9 ProblemId : 1344 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2017-06-25 01:18:06

問題文

フィボナッチ数列の第 $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 \leq N \leq 5000000 = 5 * 10^{6}$
$2 \leq M < 2^{31}$

出力

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

サンプル

サンプル1

入力

10 20

出力

$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

出力

サンプル3

入力

30 17

出力

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

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

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力