НОД массива ⇐ JAVA

[Anonymous]

Вам дан массив A целых чисел размера N. Вам будут заданы Q-запросы, в которых каждый запрос представлен двумя целыми числами L, R. Вам нужно найти НОД (наибольший общий делитель) массива после исключения части из диапазона от L до R включительно.

МОЙ подход:

Код: Выделить всё

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  r) ans = gcd(a[k], ans);
}
System.out.println(ans);
}

Но этот подход дает мне Ошибку превышения лимита времени.
Как я могу улучшить свой алгоритм?