数组的GCD

Question

给出一个大小为N的整数数组A.您将得到Q查询，其中每个查询由两个整数L，R表示。您必须找到gcd（最大公约数）不包括部分从范围左至右包容性的后阵列

我的方法：

public static int gcd(int a ,int b) { 
    if(b == 0) return a; 
    return gcd(b, a % b); 
} 

for(int j = 0; j < Q; j++) { 
    int l = in.nextInt(); 
    int r = in.nextInt(); 
    ans = 0; 
    for(int k = 1; k <= n; k++) { 
     if(k < l || k > r) ans = gcd(a[k], ans); 
    } 
    System.out.println(ans); 
} 

但这种做法给我时间超出限制的错误，我怎样才能提高我的alogrithm

Answer 1

您可以预先计算gcd为每个pre修复和后缀（我们称之为gcdPrefix和gcdSuffix）在O(n * log MAX_A)时间（只需从左到右迭代数组并存储当前的gcd，然后从右到左执行相同的操作）。 (L, R)查询的答案是gcd(gcdPrefix[L - 1], gcdSuffix[R + 1]）（因此每个查询的操作为O(log MAX_A)）。总时间复杂度为O((n + q) * log MAX_A)。我认为它应该足够快。