Fibonacci 数列升级版

题目描述

大家都知道 Fibonacci 数列吧,f1=1,f2=1,f3=2,f4=3,...,fn=fn1+fn2f_1=1,f_2=1,f_3=2,f_4=3,...,f_n=f_{n-1}+f_{n-2}

现在问题很简单,输入nnmm,求 fnmodmf_n \bmod m

输入

输入 nn, mm

输出

输出 fnmodmf_n \bmod m

样例

样例输入

5 1000

样例输出

5

提示

对于 100% 的数据, 1n2×109,1m109+101 \le n \le 2 \times 10^9,1 \le m \le 10^9 + 10

3 条评论

  • @ 2024-2-16 12:14:37

    你没有说明题目标题,请在前面用一级标题写一下

    • @ 2023-12-31 10:23:53

      这不是李老师的题目吗,直接拿过来

      • @ 2024-1-10 21:20:47

        李老师的哪个题? 我这个题的数据有 10910^9,要用矩阵快速幂,直接递推的话会TLE。

        如果真的重复了,请告知我一声,谢谢。

      • @ 2024-2-16 12:13:59

        没事了@

    • @ 2023-12-26 18:06:18

      简单的斐波那契数列。

      算法:矩阵乘法矩阵快速幂

      • 1