斐波那契数列的若干性质

蓝桥杯斐波

题目
斐波那契数列大家都非常熟悉。它的定义是:

  对于给定的整数 n 和 m,我们希望求出:
  f(1) + f(2) + ... + f(n) 的值。但这个值可能非常大,所以我们把它对 f(m) 取模。
但这个数字依然很大,所以需要再对 p 求模。
输入格式
  输入为一行用空格分开的整数 n m p (0 < n, m, p < 10^18)
输出格式
  输出为1个整数,表示答案
样例输入
2 3 5
样例输出
0
样例输入
15 11 29
样例输出
25

mod 下快乘

ll mul(ll a,ll b,ll mod){
    a%=mod,a+=mod,a%=mod;
    b%=mod,b+=mod,b%=mod;
    if(a<b) swap(a,b);
    ll ret=0;
    while(b){
        if(b&1)ret=(ret+a)%mod;
        a=(a<<1)%mod;
        b>>=1;
    }return ret;
}

题解

两条重要性质

余数推导

=>

其他性质

,则

性质

通项公式

恒等式

非常著名

数论相关

证明

其他

算法竞赛之路 文章被收录于专栏

整理、记录算法竞赛的好题

全部评论

相关推荐

07-23 12:04
门头沟学院 Java
现在是很缺人吗
码农索隆:缺分母,不缺分子,这样好作为炫耀的资本
点赞 评论 收藏
分享
zzzzhz:兄弟你先猛猛投简历至少三百家,能约到面试就去面。最近可以速成智能小车,智慧家居烂大街的项目,不需要自己写,只需要把里面的代码讲解看明白就行。把其中涉及到的八股文都拿出来单独背一下,我去年找工作就一个智能小车智慧家居找了10k差不多。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 17:13
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务