Переберемо значення відповіді знизу вгору. Для кожного від до 10^6 подивимось на позиції елементів масиву, кратних . Якщо дві такі позиції p < q обидві лежать усередині запиту, то в цьому запиті знайдеться пара з \gcd \ge d.
Отже, для кожного достатньо розглянути лише сусідні позиції кратних: якщо в запиті є дві позиції кратних , то є й дві сусідні такі позиції. Це дає набір «кандидатів»: трійок (p, q, d), де і — сусідні позиції кратних .
Тоді відповідь на запит (l, r) дорівнює
Скільки кандидатів? Для фіксованого їх на одиницю менше, ніж кратних у масиві, а загальна кількість кратних по всіх дорівнює \sum_i \tau(a_i), де — кількість дільників. При a_i \le 10^6 середнє невелике, тому кандидатів близько кількох мільйонів — цілком прийнятно. Позиції кратних для всіх будуються одним «решітчастим» проходом: для кожного перебираємо d, 2d, 3d, \ldots і збираємо позиції елементів із такими значеннями (заздалегідь склавши список позицій для кожного значення).
Відповіді на запити. Задача звелася до класичної офлайнової: маємо набір трійок (p, q, d) і запити (l, r); треба знайти максимум серед кандидатів із q \le r і p \ge l.
Відсортуємо і кандидатів, і запити за правою межею. Проходимо від до , додаючи всі кандидати з q \le r у структуру, індексовану позицією , зі значенням (беремо максимум при збігу). Тоді запит — це максимум на суфіксі , який дає дерево відрізків або дерево Фенвіка, налаштоване на суфіксний максимум.
Загальна складність — приблизно \mathcal{O}(A \log A + K \log n + m \log n), де A = 10^6, а — кількість кандидатів.