0
已解决
张恩泽
高级天翼
高级天翼
5307 Fibonacci 第 n 项 经验值:1600
题目描述 Description
大家都知道 Fibonacci 数列吧,f1=1f_1=1f1=1,f2=1f_2=1f2=1,f3=2f_3=2f3=2,f4=3f_4=3f4=3,…\ldots…,fn=fn−1+fn−2f_n=f_{n-1}+f_{n-2}fn=fn−1+fn−2。
现在问题很简单,输入 nnn 和 mmm,求 fnmodmf_n\bmod mfnmodm。
输入描述 Input Description
输入 n,mn,mn,m。
输出描述 Output Description
输出 fnmodmf_n \bmod mfnmodm。
样例输入 Sample Input
5 1000
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
对于 100%100\%100% 的数据, 1≤n≤2×109,1≤m≤109+101\le n \le 2\times 10^9, 1\le m \le 10^9+101≤n≤2×109,1≤m≤109+10。
这一题本来用string定义fib数组的,但是发现不能直接模m
改用int后,RE50分
//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
string f[250000];
long long n, m;
int a[101],b[101],c[101];
string Plus(string x,string y){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
a[0]=x.size(),b[0]=y.size();
for(int i=1;i<=a[0];i++){
a[i]=x[a[0]-i]-'0';
}
for(int i=1;i<=b[0];i++){
b[i]=y[b[0]-i]-'0';
}
c[0]=max(a[0],b[0]);
int jw=0;
for(int i=1;i<=c[0];i++){
c[i]=a[i]+b[i]+jw;
jw=c[i]/10;
c[i]%=10;
}
if(jw!=0){
c[++c[0]]=jw;
}
string ans="";
for(int i=c[0];i>=1;i--){
ans+=char(c[i]+'0');
}
return ans;
}
int main() {
// freopen ("题目名.in", "r", stdin);
// freopen ("题目名.out", "w", stdout);
cin >> n >> m;
f[1] = f[2] = 1;
for (int i = 3; i <= n; i ++) {
f[i] = (f[i - 1] + f[i - 2]) % m;
}
cout << f[n];
// fclose (stdin);
// fclose (stdout);
return 0;//好习惯!
}
各位dalao讲解一下string怎么模int