快速加倍查找斐波那契数，函数在 C++ 中不起作用

Question

我正在学习这个算法来计算斐波那契数列中的第 n 个数。这是我的代码，

#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007

long long int fib(long long int n)
{
    if(n < 2)
        return n;
    if(n == 2)
        return 1;
    long long int k = n/2;
    long long int a = fib(k+1);
    long long int b = fib(k);
    if(n%2 == 1)
        return (((a*a)%MOD) + ((b*b)%MOD))%MOD;
    else
        return (b*((2*a - b)%MOD))%MOD;

}

int main()
{
    //fibonacci series : 0,1,1,2,3,5,8,13..
    long long int n;
    scanf("%lld",&n);
    printf("%lld\n", fib(n));
    return 0;
}

它适用于较小的 no.s 但对于较大的 n 值，它的打印 -ve no.s 作为输出。

n = 10000000
fib(n) = -509810513

我不明白 -ve no.s 的值在哪里，因为我认为我正确地应用了 % 运算符，没有任何数据类型溢出。有谁帮我找出错误。

Answer 1

有取模，

long long int a = fib(k + 1);
long long int b = fib(k);

a >= b 不一定是真的，（2 * a >= b 也不是）。

所以

return (b * ((2 * a - b) % MOD)) % MOD;

可能return负数。

Answer 2

这应该可以解决 (2*a - b) < 0 的问题。它会为 n = 10000000 生成正确答案，即 490189494。

#define MOD 1000000007

long long int fib(long long int n)
{
long long int a, b, k;
    if(n < 2)
        return n;
    if(n == 2)
        return 1;
    k = n/2;
    a = fib(k+1);
    b = fib(k);
    if(n%2 == 1)
        return (((a*a)%MOD) + ((b*b)%MOD))%MOD;
    else{
        k = (2*a - b)%MOD;
        if(k < 0)
            k += MOD;
        return((b*k)%MOD);
    }
}

快速加倍查找斐波那契数，函数在 C++ 中不起作用

Fast Dobuling to find Fibonacci number, function not working in C++

c++

fibonacci

modulus