Wie können wir das letzte erreichen, z.B. 6 Ziffern der N-ten Fibonacci-Nummer in O (logN) Zeit?

Question

Ich habe eine Aufgabe in einem Online-Test mit wettbewerbsfähigen Programmier-Herausforderungen gesehen (kann leider nicht wo), die letzten (am wenigsten signifikanten) 6 Ziffern der N-ten Fibonacci-Nummer zu produzieren.

Ich habe es geschafft mit der folgenden Lösung zu kommen:

#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; 
} 

die leider O(N) Zeitkomplexität hat und starten ziemlich langsam für Eingaben wie in der letzten Zeile auszuführen: N> 10000000.

Weiß jemand, wie dies in O(logN) erreicht werden kann?

Answer 1

Es gibt einen Algorithmus, der O (log_n) Zeit nimmt, um die n-te Fibonacci-Zahl mit Q-Matrix zu berechnen. Sie können einen Blick auf http://kukuruku.co/hub/algorithms/the-nth-fibonacci-number-in-olog-n werfen, die einzige Änderung, die Sie benötigen, ist sicherzustellen, dass es nur die letzten 6 Ziffern produziert.