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

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

如果您只需要最后一位数字，则无需为其存储整个数字。

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;

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

Answer 2

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个数的末位计算成数组，然后return [=11=该数组中的第 ] 个数字。

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

How do I find the last digit of a very big number that is calculated by a formula?

c++

fibonacci