所以,这是问题所在：

给定一个数字n我需要计算递归计算该数字的斐波纳契所需的调用量,并仅输出给定基数中的最后一位数作为小数.输入为2个数字,第一个是数字n,第二个是输出所在的基数.输出应该是大小写数字,第一个输入,第二个输入和计算结果.当第一个条目等于第二个等于0的条目时,程序应该退出.例如：

输入：
0 100
1 100
2 100
3 100
10 10
3467 9350
0 0

输出：
案例1：0 100 1
案例2：1 100 1
案例3：2 100 3
案例4：3 100 5
案例5：10 10 7
案例6：3467 9350 7631

在尝试解决这个问题时,我已经达到了以下公式.作为c(n)它将在基数b中进行的调用次数的最后一位数,我们得到：
c(n)=(c(n-1)c(n-2)1)mod b

问题是n可以是从0到2 ^ 63 – 1的任何值,所以我真的需要代码有效.我尝试过以迭代方式或使用动态编程,但是虽然它给了我正确的输出,但它并没有给我足够短的时间.这是我的代码：

迭代

#include <iostream>
#include <vector>

using namespace std;

int main(){
    vector<unsigned long long int> v;
    unsigned long long int x,y,co=0;
    cin >> x >> y;
    while(x||y){
        co++;
        v.push_back(1);
        v.push_back(1);
        for(int i=2;i<=x;i++) v.push_back((v[i-1]+v[i-2]+1)%y);
        cout << "Case " << co << ": " << x << " " << y << " " << v[x] << endl;
        cin >> x >> y;
        v.clear();
    }
    return 0;
}

动态编程

#include <iostream>
#include <vector>

using namespace std;

vector<unsigned long long int> v;

unsigned long long c(int x, int y){
    if(v.size()-1 < x) v.push_back((c(x-1,y) + c(x-2,y) + )%y);
    return v[x];
}

int main(){
    int x,y,co=0;
    cin >> x >> y;
    while(x||y){
        co++;
        v.push_back(1);
        v.push_back(1);
        cout << "Case " << co << ": " << x << " " << y << " " << c(x,y) << endl;
        cin >> x >> y;
        v.clear();
    }
    return 0;
}

x和y分别为n和b,v保存c(n)的值

解决方法:

序列中的每个c都小于b.因此,c的值有可能存在.因此,一对连续元素[ck,ck 1]可以具有b2个可能的值.因此,如果你从头开始计算c1,c2,c3 ……你必须在序列开始重复之前计算最多b2个;你会得到一个等于早期[cj,cj 1]的[ck,ck 1].

然后你知道周期的长度,称之为S,你知道所有n的cn = c((n-j)mod S)j>学家这应该会减少你的工作量.