數組的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)。我認爲它應該足夠快。