c++ - 在亚线性时间内计算类似斐波那契的函数

Question

问题来了:

给定一个数字 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
案例六:3467 9350 7631

在尝试解决此问题时，我得出了以下公式。作为 c(n) 基数 b 中调用次数的最后一位，我们有:

c(n) = (c(n-1) + c(n-2) + 1) 模 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)的值

Answer 1

序列中的每个 c 都小于 b。所以 a c 的值有 b 种可能性。所以一对连续的元素 [c_k, c_k+1] 可以有 b² 可能的值。所以如果你从头开始计算c₁, c₂, c₃...你最多需要计算b< sup>2 在序列开始重复之前；你会得到一个 [c_k, c_k+1] 等于之前的 [c_j, c_{j +1}].

然后你知道循环的长度，称它为 S，你知道 c_n = c_{((n-j)mod S)+j} 对于所有 n > j。这应该会大大减少您的工作量。