c++ - 如何找到由公式计算的非常大的数字的最后一位？

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

Fibonacci 数遵循一种模式，即最后一位数字每 60 个数字重复一次。参见 http://mathworld.wolfram.com/FibonacciNumber.html

The sequence of final digits in Fibonacci numbers repeats in cycles of 60. The last two digits repeat in 300, the last three in 1500, the last four in 15000, etc. The number of Fibonacci numbers between n and 2n is either 1 or 2 (Wells 1986, p. 65).

Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, pp. 61-67, 1986.

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