查找第n個fib數，在O（logn）

Question

我想解決這個問題： SPOJ problem。

經過一番研究，但是我發現它歸結爲第n個FIB數量的簡單計算，正可以得到真正的大，以便爲O（n）解決方案將沒有任何好處。周圍的Googling我發現，你可以計算出O（LOGN）第n FIB數量，也是一個代碼示例，正是這麼做的：

long long fibonacci(int n) 
{ 
    long long fib[2][2]= {{1,1},{1,0}},ret[2][2]= {{1,0},{0,1}},tmp[2][2]= {{0,0},{0,0}}; 
    int i,j,k; 
    while(n) 
    { 
     if(n&1) 
     { 
      memset(tmp,0,sizeof tmp); 
      for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++) 
         tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j]); 
      for(i=0; i<2; i++) for(j=0; j<2; j++) ret[i][j]=tmp[i][j]; 
     } 
     memset(tmp,0,sizeof tmp); 
     for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++) 
        tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j]); 
     for(i=0; i<2; i++) for(j=0; j<2; j++) fib[i][j]=tmp[i][j]; 
     n/=2; 
    } 
    return (ret[0][1]); 
} 

我試圖修改它的問題，我仍然獲得WA：http://ideone.com/3TtE5m

我在計算模運算錯誤嗎？或者是其他問題？

Answer 1

你的意思是我希望第nth斐波那契。

爲了做到這一點，你需要Fibonacci數的矩陣分解描述here。

的基本思想是你把唐納德·E Knuth的矩陣形式的身份爲斐波那契數是：

，而是用傳統的方式計算fibonnaci數字，你會試圖找到（k）的冪的矩陣，其中k被要求給定數量。

因此，這是解決K矩陣乘法問題，而不是真正的幫助，因爲我們可以更容易的方式做到這一點。

但是等等！我們可以優化矩陣乘法。我們可以首先將其平方，然後進行乘法的一半，而不是進行k乘法。我們可以繼續這樣做。所以如果給定的數字是2^a，那麼我們可以通過一個步驟來完成。通過保持矩陣的平方。

如果矩陣不是正方形，我們可以做一個數字的二進制分解，看看是否採取給定矩陣的平方成最終產品或沒有。

在你的情況下，每個相乘後，你還需要模運算符123456適用於每個矩陣數。

希望我的解釋有幫助，如果沒有看到更清晰和更長的鏈接。

其實是有任務的又一個警告，因爲你被要求提供給定數量的一些Fibonacci數模。你還應該證明，提醒每個矩陣元素不會改變操作。換句話說，如果我們乘以矩陣並提醒我們實際上仍然得到斐波納契數字提醒。但由於提醒操作是分佈式的，所以實際上確實產生了正確的結果。

Answer 2

有一個很簡單的算法，只使用整數：

long long fib(int n) { 
    long long a, b, p, q; 
    a = q = 1; 
    b = p = 0; 
    while (n > 0) { 
     if (n % 2 == 0) { 
      long long qq = q*q; 
      q = 2*p*q + qq; 
      p = p*p + qq; 
      n /= 2; 
     } else { 
      long long aq = a*q; 
      a = b*q + aq + a*p; 
      b = b*p + aq; 
      n -= 1; 
     } 
    } 
    return b; 
} 

這是基於identities of the Lucas sequence。