Задачка на запросики

Правка ru3, от omoyamo, 2019-11-11 21:05:31

В очень узких кругах возникла интересная (нет) таска на запросы. Сможете ли вы ее решить?

Дан массив размера n из целых неотрицательных чисел. Дано q запросов одного вида.

Запрос на подотрезке (L, R) — нужно вывести max[ lcm(a, b) — gcd(a, b) ], где a и b — какие-то числа на подотрезке с L по R. Cчитать что gcd(0, 0) == 0 и lcm(0, 0) = 0.

n <= 10^5, q <= 10^5

Напишите свои идеи в комментариях.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский omoyamo 2019-11-11 21:06:30 36 Tiny change: ' <= 10^5\n\n' -> ' <= 10^5\n#### Write your ideas in comments.'
ru3 Русский omoyamo 2019-11-11 21:05:31 41 Мелкая правка: ' <= 10^5\n' -> ' <= 10^5\n\n#### Напишите свои идеи в комментариях.'
en1 Английский omoyamo 2019-11-11 21:03:13 472 Initial revision for English translation
ru2 Русский omoyamo 2019-11-11 20:52:11 46 Мелкая правка: ' q <= 10^5' -> ' q <= 10^5\n#### (считать что gcd(0, 0) == 0 и lcm(0, 0) = 0'
ru1 Русский omoyamo 2019-11-11 19:12:46 388 Первая редакция (опубликовано)