No.526 フィボナッチ数列の第N項をMで割った余りを求める
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 643
作問者 :
Leonardone
/ テスター :
くれちー
タグ : / 解いたユーザー数 643
作問者 :
Leonardone
/ テスター :
くれちー
問題文最終更新日: 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 \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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。