题目描述
斐波那契数列大家都非常熟悉。它的定义是：
f(x) = 1 .... (x=1,2)
f(x) = f(x-1) + f(x-2) .... (x>2)
对于给定的整数 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
样例代码
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define AA first
#define BB second
#define OP begin()
#define ED end()
#define SZ size()
#define SORT(x) sort(x.OP,x.ED)
#define SQ(x) ((x)(x))
#define SSP system(“pause”)
#define cmin(x,y) x=min(x,y)
#define cmax(x,y) x=max(x,y)
typedef long long LL;
typedef pair PII;
const double eps=1e-8;
const double INF=1e20;
const double PI=acos( -1. );
const int MXN = 50;
const LL MOD = 1000000007;
LL llmul( LL a,LL b,LL mod ) {
a%=mod;a+=mod;a%=mod;
b%=mod;b+=mod;b%=mod;
if ( a*>n>>m>>mod )
cout<<( solve( n+2,m,mod )-1+mod )%mod<<endl;
return 0;
}**
struct matrix {
LL x[3][3];
matrix() {memset( x,0,sizeof x );}
};
matrix mmul( matrix &A,matrix &B,LL mod ) {
matrix ret;
for ( int i=1; i<=2; i++ )
for ( int j=1; j<=2; j++ )
for ( int k=1; k<=2; k++ )
ret.x[i][j]=( ret.x[i][j]+llmul( A.x[i][k],B.x[k][j],mod ) )%mod;
return ret;
}
matrix E;
matrix A;
LL fib( LL n,LL mod ) {
matrix O=E,B=A;
while ( n ) {
if ( n&1 )O=mmul( O,B,mod );
B=mmul( B,B,mod );
n/=2;
}
return O.x[1][2];
}
//[(2_3)%5]%3=1 //(2%3)_(3%3)=0
LL solve( LL n,LL m,LL mod ) {
//f(n)%f(m)%mod
LL t=n/m;
//(f(m-1)^t_f(n%m))%f(m)%mod; //f(i)2%f(i-1)=(-1)(i+1) LL p=t/2,q=t%2; //{f(m-1)q_(-1)(pm)_f(n%m)}%f(m)%mod LL fuhao=p_m%2==0?1:-1;
if ( q==0 ) {
LL ans=fib( n%m,mod )_fuhao; ans%=mod; ans+=mod; return ans%mod; } if ( n%m==0 )return 0; //f(m-1)_f(n%m)fuhao%f(m)%mod // cout<fib(n%m,mod111111)fuhao%fib(m,mod<<5)%mod<<endl;
// cout<<fib(m-1,mod<<5)<<””<”<<fuhao<<”%”<<fib(m,mod<<5)<<”%”<<mod<<endl;
// cout<<fib(n%m,mod<<5)fib(m-1,mod<<5)/fib(m,mod<<5)<y)%mod
//a=[x/y]
LL x=(llmul(fib(n%m,mod),fib(m-1,mod),mod)*fuhao%mod+mod)%mod;
LL y=fib(m,mod);
LL a=fib(n%m-1,mod);
if(n%m%2==0)a–;
if(fuhao<0)a++;
a=(a%mod+mod)%mod;
// cout<<a<<endl;
return ((x-llmul(a,y,mod))%mod+mod)%mod;
}
int main() {
int i,j;
A.x[1][2]=A.x[2][1]=A.x[2][2]=1;
E.x[1][1]=E.x[2][2]=1;
LL n,m,mod;
while ( cin>>n>>m>>mod )
cout<<( solve( n+2,m,mod )-1+mod )%mod<<endl;
return 0;
}