6

我有以下问题：我应该计算一个斐波那契数模另一个给定的数字。我知道 Pisano 时期，我正试图在这里实现它。这是代码：

#include <iostream>
#include <cstdlib>
long long get_fibonaccihuge(long long n, long long m) {
    long long period = 0;
    if (m % 2 == 0) {
        if(m / 2 > 1)
        period = 8 * (m / 2) + 4;
        else
        period = 3; 
    }
    else{
        if(((m + 1) / 2) > 1)
        period = 4 * ((m + 1) / 2);
        else
        period = 1;
    }

    long long final_period = n % period;



    long long array_fib[final_period];
    array_fib[0] = 1;
    array_fib[1] = 1;
    for (long long i = 2; i < final_period; ++i) {
        array_fib[i] = (array_fib[i-1] + array_fib[i-2]) % m;
    }

    return array_fib[final_period - 1];
}

int main() {
    long long n, m;
    std::cin >> n >> m;
    std::cout << get_fibonaccihuge(n, m) << '\n';
}

它适用于小型测试，但问题是它无法通过以下测试：

281621358815590 30524

我不知道为什么。关于算法的任何建议，我都参考了这个页面。当我在构建它时。

我收到的错误是：错误的结果。

预期：11963 我的结果：28651

4

1 回答 1

2

除非您的任务是使用 Pisano 周期，否则我建议您使用更常见的已知方法以 log2(n) 步骤计算第 n 个斐波那契数（通过 2*2 矩阵的计算能力：https://en.wikipedia .org/wiki/Fibonacci_number#Matrix_form）。

有两个原因：

  1. 这是一个更简单的算法，这意味着调试程序会更容易
  2. 对于您作为示例提到的数字，它应该更快（log2(n) 大约为 50，m/2 明显更多）。
于 2016-04-17T11:31:05.933 回答