GCD付きの大きなフィボナッチ

Question

数日前にプログラミングの課題でこの質問を受けました。

Iは、バックエンドで20のうち、渡された唯一のテストケースを得ました。これは私が配列の要素のサイズは10^9フィボナッチ配列のサイズが最大10^6可能ですので、私のコードが間違っている理由は、私が知っていると思う私の解決策

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

} 

です。そして、私が大きなインデックスにアクセスしているときはいつでも、配列外の例外が発生します。しかし、私はこれを解決する方法を知らない。他のアプローチはありますか？

Answer 1

範囲クエリに関する質問は通常、セグメントツリーで解決されます。
これは競争力のあるプログラミングから始めるのに適した基本的なデータ構造です。

ここで、私は1つの良い特性を述べたいと思います。 Fibo（a [l]））= Fibo（GCD（a [l]、a [l + 1]）、Fibo 、...、a [r]））。

プレrequiste：セグメントツリー=>GeeksForGeeks
2（ログn）Oで高速フィボナッチの検索を使用して、範囲の
1.発見GCD。

すべて合格の場合とC++での私のコードは：HackerEarth