大型斐波那契与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

回答

相关问题