问题标题: 酷町堂:5307 Fibonacci 第 n 项

0
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 mfn​modm。

输入描述 Input Description

输入 n,mn,mn,m。

输出描述 Output Description

输出 fnmodmf_n \bmod mfn​modm。

样例输入 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


0
已采纳
汪恺恒
汪恺恒
中级启示者
中级启示者

要用数论

因为n<=10^9,所以没法定义数组,string%int也不管用

很复杂,建议你问老师

 

我要回答