当前位置:首页 > 数学 > 矩阵 > 正文
SSOJ2922Fibonacci第n项
3294+

题目大意:求Fibonacci数列第n项,n很大,结果很大,输出模m的结果。

题目描述

大家都知道 Fibonacci 数列吧,f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2。

现在问题很简单,输入 n和 m,求 fn mod m 。

输入格式

输入 n,m。

输出格式

输出 fn mod m。

样例

5 1000
5

数据范围与提示

对于 100%的数据, 1≤n≤2×109,1≤m≤109+10。

解题思路

斐波拉契数列:1、1、2、3、5、8……从第三项开始等于前两项之和。

定义矩阵:

a b

0 0

如何得到矩阵:

b a+b

0 0

只需要乘以矩阵:

0 1

1 1

乘1次,就矩阵左上角就第2项目,乘n-1次,矩阵左上角就是第n项。

程序实现

About

坚决不Copy代码!

本文标签:,,,,

SSOJ2922Fibonacci第n项:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!