Быстрый алгоритм вычисления последней цифры Фибоначчи

Question

Я пытаюсь решить Фибоначчи с помощью Java, но мой код занимает много времени с большими числами.

Описание проблемы Задача.Дано целое число ?, найдите последнюю цифру ?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));
}}

Мой код завершится ошибкой, если input = 613455, чтобы получить значение и максимально допустимое значение, потребуется 30 секунд.время составляет 1,5 секунды.

Мне пришлось использовать большое целое число, потому что долго не достаточно.

Answer 1

Ваша реализация действительно наивна, потому что вас просят получить последнюю цифру числа Фибоначчи, а не само число Фибоначчи.Вам нужно только отслеживать последнюю цифру, другие цифры не имеют значения.

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

private static int getFibonacciLastDigit(int n) {
    if (n <= 1) {
        return n;
    }
    int first = 0;
    int second = 1;
    int temp;

    for (int i = 1; i < n; i++) {
        temp = (first + second) % 10;
        first = second;
        second = temp;
    }
    return second;
}

Answer 2

В последней цифре чисел Фибоначчи есть цикл.Это повторяется для каждых 60 номеров.Так что просто создайте таблицу из последней цифры из первых 60 чисел, затем выполните операцию по модулю 60 для входа и поиска по таблице.

Вы можете увидеть цикл в любой онлайн (или автономной) таблице Фибоначчиномера.Одна ссылка внизу.

Для построения таблицы для каждого вычисленного числа вы можете вычесть 10, если оно больше 9, поскольку вам нужна только последняя цифра, а последняя цифра каждого номера зависит только от последней цифры.из двух предыдущих номеров.Вы можете использовать int математику (вам не нужно ни long, ни BigInteger).

Ссылка: Первые 300 чисел Фибоначчи, с учетом