Вам дан массив A целых чисел размера N. Вам будут заданы Q запросов, в которых каждый запрос представлен двумя целыми числами L, R. Вам нужно найти НОД (наибольший общий делитель) массива после исключения части из диапазона от L до R включительно N ≤ 10^6, 1 ≤ Q ≤ N,
Мой подход:
Вычислить префикс НОД, а затем суффикс НОД и вернуть ответ.
Код:
Код: Выделить всё
public static int gcd(int a , int b){
if(b==0) return a;
return gcd(b,a%b);
}
for(int i=1;i0;i--){
suff[i] = gcd(a[i],suff[i+1]);
}
for(int i=0;i