大型斐波那契與GCD

幾天前，我在編程挑戰中得到了這個問題。大型斐波那契與GCD

我只拿到一個測試情況下，在後端通過了20。這是我的解決方案

import java.util.Scanner; 
class TestClass { 
    public static void main(String args[]) throws Exception { 
     Scanner s = new Scanner(System.in); 
     int size = s.nextInt(); 
     int[] input = new int[size]; 


     long[] fiboDp = new long[1000000]; 
     fiboDp[0] = 0; 
     fiboDp[1] = 1; 

     for(int index = 2;index<1000000;++index) { 
      fiboDp[index] = (fiboDp[index-1]%1000000007+fiboDp[index-2]%1000000007)%1000000007; 

     } 

     int query = s.nextInt(); 

     for(int index = 0; index < size; ++index) { 
      input[index] = s.nextInt(); 
     } 

     long[][] dpans = new long[size][size]; 

     for(int i = 0; i < size; ++i) { 
      long gcdAns = fiboDp[input[i]]; 

      for(int j = i; j < size;++j) { 
       if(i == j) { 
        dpans[i][j] = gcdAns; 
       } 
       else { 
        dpans[i][j] = gcd(dpans[i][j-1],fiboDp[input[j]]); 
       } 
      } 
     } 

     while(query > 0) { 
      int left = s.nextInt(); 
      left = left-1; 
      int right = s.nextInt(); 
      right = right-1; 

      // long ansGCD = fiboDp[input[left]]; 
      // for(int index =left ; index<= right;++index) { 
      //  ansGCD = gcd(ansGCD,fiboDp[input[index]]); 
      // } 
      System.out.println(dpans[left][right]); 
      query--; 
     } 
    } 

    static long gcd(long a, long b) { 
     return b == 0? a : gcd(b,a%b); 
    } 

}

我想我知道爲什麼我的代碼是錯誤的，因爲數組的元素大小是10^9斐波那契陣列尺寸可達到10^6。而且每當我訪問較大的索引時，都會發生數組越界的異常。但我不知道如何解決這個問題。還有其他方法嗎？

來源

2017-07-16 Brij Raj Kishore

當然，你在這裏已經足夠長的時間知道，這樣的問題是不適合我們的格式。 –

儘管我已經在1年前提交了帳戶，但我通常不知道在哪裏提出這些問題。 https://meta.stackexchange.com/questions/129598/which-computer-science-programming-stack-exchange-do-i-post-in。在這裏，我已閱讀，我認爲這將是適當的地方問。如果沒有，那麼請指導我在哪裏問。謝謝 –

所以堆棧溢出是針對有關實際代碼的具體問題。你的問題太廣泛了。我建議，特別是鑑於這是一個編程挑戰，您需要花費一些時間在調試器中，並縮小問題範圍，使其不超過十行。 –

帶範圍查詢的問題通常使用分段樹來解決。
從競爭性編程開始，這是一個很好的基本數據結構。

現在，我想陳述一個好的財產，即。 GCD（a [1]，a [1 + 1]），Fibo（a [1]），...，Fibo（a [r]））= Fibo ，...，a [r]））。

預requiste：
1.一個使用範圍線段樹=>GeeksForGeeks
2.查找斐波納契的查找GCD快速在O（log n）的。

我的代碼在C++與全部通過情況：HackerEarth

來源

2017-07-31 05:29:20

大型斐波那契與GCD

回答

相關問題