小编kat*_*nas的帖子

(初学者在这里)

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

输入:

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(通过使用这个公式可以在O(log n)中找到第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 …