Задача про НОД и запросы

Правка ru1, от waipoli, 2023-07-15 21:45:03

Дан массив целых чисел a(len(a) < 10^5, 1 <= a[i] <= 10^9)

дано q запросов двух типов

В первом из них заданы два числа x(0 <= x < len(a)) и y(1 <= y <= 10^9) требуется изменить елемент массива а с позицией x на y

Во втором же заданы два числа: l,r(0 <= l < len(a), 0<= r < len(a), l < r) требуется найти два разных таких индекса x1,x2 принадлежащих отрезку от l до r включительно таких что их НОД будет максимально возмжным из всех пар(вывести его)

Я умею решать эту задачу полным перебором O(q*n^2) но мне лично интересно узнать есть ли решение за нормальную асимптотику(O(q*log(N))).

Теги необычная задача, не знаю как решать, нод

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский waipoli 2023-07-15 21:47:50 744 Initial revision for English translation
ru1 Русский waipoli 2023-07-15 21:45:03 626 Первая редакция (опубликовано)