Не так давно мне попалась задача B с отбора на олимпиаду [Высшая проба](https://olymp.hse.ru/mmo/it) по информатике, 10 класс:↵
↵
↵
Дан массив натуральных чисел $a$ длины $n$ и $q$ запросов, $j$-й из которых содержит натуральное число $x_j$. Для $j$-го запроса требуется определить наибольшее число равных элементов в массиве $b$, полученном из $a$ следующим образом: $b_i=\lfloor\frac{a_i}{x_j}\rfloor$ для всех $i$ от $1$ до $n$.↵
↵
В оригинальной задаче ограничения следующие: $1 \leq n, q, a_i, x_j \leq 3\cdot10^5$. В таком случае я увидел следующее решение:↵
↵
<spoiler summary="Решение">↵
Определим $N =3\cdot10^5max(a_1, a_2, \dots a_n, x_1, x_2, \dots x_q)$.↵
↵
Для каждого $val\ (1 \leq val \leq N)$ посчитаем число его вхождений в $a$. Затем переберем все $1 \leq x \leq N$ и для каждого из них посчитаем ответ. Для этого заметим, что все числа вида $k \cdot x + p$, где $k, p \in \mathbb{Z}, 1 \leq p < x$ дают одинаковый результат при делении нацело на $x$. Тогда для зафиксированного $x$ можно перебрать $k$ от $0$ до $\lfloor\frac{N}{x}\rfloor$ и посчитать число вхождений чисел из отрезка $[k\cdot x, k\cdot x + x - 1]$ в $a$. Для того, чтобы избавиться от перебора за $O(N)$, построим префиксные суммы на массиве счетчиков. После подсчета можно отвечать на запросы за $O(1).$↵
↵
Тогда число операций для фиксированного $x$ будет $O(\frac{N}{x})$. Следовательно, при переборе всех $x$ от $1$ до $N$ получится сложность $O(NlogN).$↵
</spoiler>↵
↵
Но изначально условие попало ко мне в искаженном виде. А именно, ограничения были немного изменены: элементы массива и числа в запросах могли достигать стандартной отметки в $10^9$. Неожиданно, эта задача вызвала у меня затруднения. И теперь я задался вопросом: а насколько быстро её можно решать?↵
↵
↵
↵
Дан массив натуральных чисел $a$ длины $n$ и $q$ запросов, $j$-й из которых содержит натуральное число $x_j$. Для $j$-го запроса требуется определить наибольшее число равных элементов в массиве $b$, полученном из $a$ следующим образом: $b_i=\lfloor\frac{a_i}{x_j}\rfloor$ для всех $i$ от $1$ до $n$.↵
↵
В оригинальной задаче ограничения следующие: $1 \leq n, q, a_i, x_j \leq 3\cdot10^5$. В таком случае я увидел следующее решение:↵
↵
<spoiler summary="Решение">↵
Определим $N =
↵
Для каждого $val\ (1 \leq val \leq N)$ посчитаем число его вхождений в $a$. Затем переберем все $1 \leq x \leq N$ и для каждого из них посчитаем ответ. Для этого заметим, что все числа вида $k \cdot x + p$, где $k, p \in \mathbb{Z}, 1 \leq p < x$ дают одинаковый результат при делении нацело на $x$. Тогда для зафиксированного $x$ можно перебрать $k$ от $0$ до $\lfloor\frac{N}{x}\rfloor$ и посчитать число вхождений чисел из отрезка $[k\cdot x, k\cdot x + x - 1]$ в $a$. Для того, чтобы избавиться от перебора за $O(N)$, построим префиксные суммы на массиве счетчиков. После подсчета можно отвечать на запросы за $O(1).$↵
↵
Тогда число операций для фиксированного $x$ будет $O(\frac{N}{x})$. Следовательно, при переборе всех $x$ от $1$ до $N$ получится сложность $O(NlogN).$↵
</spoiler>↵
↵
Но изначально условие попало ко мне в искаженном виде. А именно, ограничения были немного изменены: элементы массива и числа в запросах могли достигать стандартной отметки в $10^9$. Неожиданно, эта задача вызвала у меня затруднения. И теперь я задался вопросом: а насколько быстро её можно решать?↵
↵
