c++ - 斐波那契数列更快，但起始数不同 (F[n]=F[n-1]+F[n-2])

Question

(这里是初学者)

我想知道如何找到序列 F[n]=F[n-1]+F[n-2] 的第 n 个数。

输入:

F[0] =  a;
F[1] =  b;
a,b < 101
N < 1000000001 
M < 8; M=10^M;

a和b是起始序列号。

n 是我需要查找的序列的第 n 个数。

M 是模数，数字很快变大所以 F[n]=F[n]%10^M，我们求余数，因为只需要第 n 个数的最后一位数

递归方法太慢了:

int fib(int n)
{
   if (n <= 1)
      return n;
   return fib(n-1) + fib(n-2);
}

O(n) 时间的动态规划解决方案也太慢了:

f[i] = f[i-1] + f[i-2];

如果序列的第一个数字是 0 和 1(第 n 个数字可以在 O(log n) 中找到)，虽然有一些解决方案可以通过使用以下公式更快地找到第 n 个数字:

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

(链接到公式和代码实现:https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)

但是如果起始数字是 25 和 60 这样的数字，这个公式就不起作用了。而且递归方法太慢了。

所以我想知道如何比 O(n) 更快地找到序列的第 n 个数。部分代码会有所帮助。

谢谢。

Answer 1

这个矩阵:

A = / 1  1 \
    \ 1  0 /

当乘以列 vector (f_n+1, f_n)时，其中f_n是斐波那契数列中的第n个数序列，将为您提供列 vector (f_n+2, f_n+1)，即它将使您前进一步。无论序列的初始元素是什么，这都有效。

例如:

/ 1  1 \ / 8 \  =  / 13 \
\ 1  0 / \ 5 /     \ 8  /

所以第n个斐波那契数是A^n-1v的第一个元素，其中v是包含f₁和f_{0 ，序列中的前两个数字。}

因此，如果您可以快速计算 A^n-1 对某个数取模，这将得到 f_n。这可以使用 Exponentiation by squaring 来完成，在 O(logn) 中有效。只需确保在每次乘法和加法之后都执行模运算，以防止数字变得太大。