斐波那契数列的若干性质

蓝桥杯斐波

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

　　对于给定的整数 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;
}

题解

两条重要性质

余数推导

=>

其他性质

若，则

性质

通项公式

恒等式

非常著名

数论相关

证明

其他