如何找到公式计算出的很大数字的最后一位？

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。《好奇与有趣数字企鹅词典》。英格兰米德尔塞克斯（Middlesex），1986年，企鹅出版社，第61-67页。

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