java - 大斐波那契数的最后一位快速算法

Question

我正在尝试使用 java 解决 Fibonacci，但我的代码需要很长时间才能处理大数。

问题描述任务。给定一个整数 𝑛，找到 𝑛th 斐波纳契数 𝐹𝑛 的最后一位(即 𝐹𝑛 mod 10)。

输入格式。输入由单个整数 𝑛 组成。

约束。 0 ≤ 𝑛 ≤ 10⁷。

输出格式。输出𝐹𝑛的最后一位。

我的代码:

public class FibonacciLastDigit {

private static int getFibonacciLastDigitNaive(int n) {
    if (n <= 1) {
        return n;
    }
    BigInteger first = BigInteger.ZERO;
    BigInteger second = BigInteger.ONE;
    BigInteger temp;

    for (int i = 1; i < n; i++) {
        temp = first.add(second);
        first = second;
        second = temp;
    }
    return second.mod(BigInteger.TEN).intValue();
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    System.out.println(getFibonacciLastDigitNaive(n));
}}

如果输入 = 613455，我的代码将失败，需要 30 秒才能获取值，并且允许的最大时间为 1.5 秒。

我不得不使用 big Integer，因为 long 不够用。

Answer 1

斐波那契数列的最后一位有一个循环。每 60 个数字重复一次。因此，只需构建前 60 个数字的最后一位数字的表格，然后对输入和表格查找进行模 60 运算。

您可以在任何在线(或离线)斐波那契数列表中看到周期。底部有一个链接。

对于构建表格，对于每个计算出的数字，如果它超过 9，您可以减去 10，因为您只需要最后一位，并且每个数字的最后一位仅取决于前两个数字的最后一位。您可以使用 int 数学(您既不需要 long 也不需要 BigInteger)。

链接:The first 300 Fibonacci numbers, factored