フィボナッチ数列の n 番目を m で割った余りを求める
フィボナッチ数列は、前の2つの項を足し合わせることで次の項を求める数列で、最初の2つの要素は 0 と 1 です:
与えられた数 n に対して、n 番目のフィボナッチ数を m で割った余りを求めてください。
ここでは m での剰余だけが必要であり、n は非常に大きな値となる可能性があります。
入力
入力は 1 行で、2 つの整数 n (0 ≤ n ≤ ) と m (1 ≤ m ≤ 50) が与えられます。
出力
プログラムは の結果を出力してください。
例
入力 | 出力 |
|---|---|
0 5 | 0 |
1 5 | 1 |
6 5 | 3 |
解説
fib(0) = 0 ⇒ 0 mod 5 = 0
fib(1) = 1 ⇒ 1 mod 5 = 1
fib(6) = 8 ⇒ 8 mod 5 = 3
Hint 1
フィボナッチ数を m で計算する場合、次の数は常に直前の2つに依存するため、ある時点でパターンが繰り返され始めます。多くの値を m で求めてみると、一周して再び同じパターンが出てくることがわかるでしょう。
Hint 2
数列がある長さで繰り返されるので、すべての値を順に計算しなくても、直接 n 番目のフィボナッチ数を求められます。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB