Как мы можем достичь последнего, например, 6 цифр N-го числа Фибоначчи в O (logN) времени?

Question

Я видел задачу по онлайн-тестированию с конкурентными задачами программирования (не могу раскрыть, к сожалению, где) для производства последних (наименее значимых) 6 цифр номера N-го Фибоначчи.

мне удалось придумать следующее решение:

#include <iostream> 
#include <cassert> 
#include <tuple> 

int solution(int N) 
{ 
    if(N == 0) return 0; 
    if(N == 1) return 1; 
    if(N == 2) return 1; 
    int a = 0; 
    int b = 1; 
    int c = 1; 

    for (int i = 3; i <= N; ++i) { 
    std::tie(a, b, c) = std::make_tuple(b, (a + b) % 1000000, (b + c) % 1000000); 
    } 
    return c; 
} 

int main() 
{ 
    assert(solution(8) == 21); 
    assert(solution(36) == 930352); 
    std::cout << solution(10000000) << std::endl; 
} 

, который, к сожалению, имеет O(N) временную сложность и начать работать довольно медленно для входов, как и в последней строке: N> 10000000.

Кто-нибудь знает, как это можно достичь в O(logN)?

Answer 1

Существует алгоритм, использующий время O (log_n) для вычисления n-го числа Фибоначчи с использованием Q-матрицы. Вы можете взглянуть на http://kukuruku.co/hub/algorithms/the-nth-fibonacci-number-in-olog-n, единственное изменение, которое вам нужно, это убедиться, что оно производит только последние 6 цифр.