我們如何才能達到最後O（logN）時間的第N個斐波納契數的6位數？

Question

我已經看到一個在線測試任務，具有競爭性的編程挑戰（不能透露不幸地在哪裏）產生第N個斐波納契數的最後（最低有效）6位數字。

我已成功地拿出了以下解決方案：

#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

有一種算法，使用Q-Matrix計算O（log_n）時間來計算第n個斐波納契數。你可以看看http://kukuruku.co/hub/algorithms/the-nth-fibonacci-number-in-olog-n，你需要的唯一改變是確保它只產生最後6位數字。