Задача про НОД и запросыProblem about GCD and queries
Разница между ru1 и en1, 744 символ(ов) изменены
Дан массив целых чиселGiven an array of integers a (len(a) < 10^5, 1 <= a[i] <= 10^9).↵
↵
дано q запросов двух типов↵
↵
В первом из них заданы два числаThere are q queries of two types:↵
↵
    In the first type, two numbers x (0 <= x < len(a)) иand y (1 <= y <= 10^9) требуется изменить елемент массива а  с позициейare given. You need to change the element of the array a at position x наto y.↵
↵
Во втором же заданы два числа: l,r    In the second type, two numbers l and r are given (0 <= l < len(a), 0 <= r < len(a), l < r) требуется найти два разных таких индекса x1,x2 принадлежащих отрезку от l до r включительно таких что их НОД будет максимально возмжным из всех пар(вывести его)↵
↵
Я умею решать эту задачу полным перебором. You need to find two different indices x1 and x2 belonging to the segment from l to r (inclusive) such that their greatest common divisor (GCD) is the largest possible among all pairs (output the GCD).↵
↵
I know how to solve this problem with brute force O(q*n^2) но мне лично интересно узнать есть ли решение за нормальную асимптотику, but I am personally interested in finding a solution with a better complexity (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 Первая редакция (опубликовано)