배열의 GCD

Question

크기 N의 정수 A 배열이 주어집니다. 각 쿼리가 두 개의 정수 L, R로 표시되는 Q 쿼리가 제공됩니다. gcd (Greatest Common Divisor)를 찾아야합니다. 포함 R에 범위 L의 부분을 제외한 후 배열

MY 접근 :

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

그러나이 방법은 나에게 내가

Answer 1

당신은 미리 계산 할 수 있습니다 내 고리즘을 향상시킬 수있는 방법은 시간 제한 초과 오류를주는 각 사전에 대한 gcd 수정 및 접미사 (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)입니다. 나는 그것이 충분히 빨라야한다고 생각한다.