题目描述
斐波那契数列大家都非常熟悉。它的定义是:
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<1018
测试数据不超过100组
输入样例1:
2 3 5
输出样例1:
0
输入样例2:
15 11 29
输出样例2:
25
不会写,蹲一个大佬,我这个在数字小的时候还能对,数字大了就超时了
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,m,p;
while(cin>>n>>m>>p){
if(m>n)m=n;
long long a=1,b=1,c=1,M,A=1;
m--;
for(long long i=1;i<n;i++){
c=a+b;
a=b;
b=c;
A+=a;
if(m==i){
M=a;
}
}
cout<<(A%M)%p<<endl;
}
}
可以,负数还行。