如何找到由公式计算的非常大的数字的最后一位数字?

Question

我有一个斐波那契问题，我想计算第 n 个斐波那契并想要它的最后一位(当我做它时得到的数字 % 10(。n将被给出，最多可以达到 10^18。

unsigned long long int nthfib(long long int n) { 
double phi = (1 + sqrt(5)) / 2; 
return round(pow(phi, n-1) / sqrt(5));
}

上面的代码，对于大 n，例如 1024，给出了一个如此大的数字，以至于我无法将其存储在变量中并找到它的 % 10。

由于时间是一个问题，我想要 O(1( 中的解决方案。

Answer 1

斐波那契数遵循最后一个数字每60个数字重复一次的模式。请参阅 http://mathworld.wolfram.com/FibonacciNumber.html

斐波那契数中的最后一个数字序列以 60 为周期重复。最后两位数字在 300 中重复，最后三位在 1500 中重复，最后四位在 15000 中重复，依此类推。n 到 2n 之间的斐波那契数是 1 或 2(Wells 1986，第 65 页(。

威尔斯，D.企鹅好奇和有趣的数字词典。米德尔塞克斯，英格兰：企鹅图书，第61-67页，1986年。

要在恒定时间内获取第n个数字的最后一位，您可以将前 60 个数字的最后数字计算到一个数组中，然后返回该数组中的第n % 60位数字。

Answer 2

如果你只想要最后一个数字，你不需要存储它的整个数字。

a = 0; // return a if n==1
b = 1; // return b if n==2
for(i=2;i<n;i++){
c = (a+b)%10;
a=b;
b=c;
}
return b;

您不是存储整个数字，而只是存储它们的最后一位数字。