c++ - 计算大斐波那契数的mod m

我收到以下两个代码的警告(缩小转换&&控制可能会到达非void函数的结尾)。但是代码会编译，当我运行它时会显示以下消息:Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)
使用上的 CLion 编译代码，而Ubuntu

// calculate F(n) mod m

#include <iostream>
#include <cmath>

long long Fiobonacci(long long n) { // Fast calculation of Fibonacci number using 'fast doubling'

    if (n == 0)
        return 0;
    else if (n % 2 == 0)
        return Fiobonacci(n / 2) * (2 * Fiobonacci(n / 2 + 1) - Fiobonacci(n / 2));
    else
        return std::pow(Fiobonacci((n + 1) / 2), 2) + std::pow(Fiobonacci((n - 1) / 2), 2);
}

long long GetPissanoPeriod(long long m){
    for (long long i = 0; i <= 6 * m ; ++i){
        if (Fiobonacci(i) % m == 0){ // if an element is zero it might be followed by a 1
            if(Fiobonacci(i+1) % m == 1)
                return i+1;
        }
    }
}

int main() {
    long long n, m;
    std::cin >> n >> m;
    long long period = GetPissanoPeriod(m);
    long long res = Fiobonacci(n % period) % m;
    std::cout << res << 'n';
}

最佳答案

请参阅下面的修改后的代码。

 #include <iostream>
 #include <cmath>
 using namespace std;
 long long pow2(long long x)
 {
     return x * x;
  }
 long long Fibonacci(long long n) { // Fast calculation of Fibonacci number using 'fast doubling'

         if (n == 0)
                 return 0;
         else if(n <= 2)
                 return 1;
         else if (n % 2 == 0)
                 return Fibonacci(n / 2) * (2 * Fibonacci(n / 2 + 1) - Fibonacci(n / 2));
        else
                 return pow2(Fibonacci((n/2 + 1) / 2), 2) + pow2(Fibonacci((n / 2)), 2);
}

 long long GetPisanoPeriod(long long m){
         for (long long i = 2; i <= m * m ; ++i){
                 if (Fibonacci(i) % m == 0){ // if an element is zero it might be followed by a 1
                         if(Fibonacci(i+1) % m == 1){
                                return i - 1;
                         }
                 }
         }
 return 1;
 }
 int main() {
         long long n, m;
         std::cin >> n >> m;
         long long period = GetPisanoPeriod(m);
         long long res = Fibonacci(n % period) % m;
         std::cout << "res" << res<<endl;
 }

由于未从GetPisanoPeriod返回值，因此控件可能到达非void函数错误的结尾。正如@JaMiT所指出的

分段错误是由于函数Fibonacci的错误终止条件引起的。
斐波那契数列定义如下。

  Fn = Fn-1 + Fn-2

具有种子值

  F0 = 0 and F1 = 1

意味着应该为n = 0和n = 1提供终止条件。
对于n = 2，您不必调用递归就可以简单地返回1。

除此之外，您可以看到斐波纳契计算公式中有更正。
在GetPisanoPeriod中，控件必须从2开始。否则它将始终返回0。

关于c++ - 计算大斐波那契数的mod m，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56729091/