Страшные числа

Автор задачи и разработчик: Сергей Щербаков

Воспользуемся решетом Эратосфена. Реализация решета Эратосфена за время $$$\mathcal{O}(n)$$$ также находит для каждого числа в отрезке минимальный простой делитель. Зная для каждого числа его минимальный простой делитель, можно факторизовать (разложить на простые) любое число $$$t$$$ за время $$$\mathcal{O}(\log t)$$$. Для этого достаточно просто делить число на минимальное простое в разложении, пока оно не станет равно $$$1$$$.

Заметим, что максимальное возможное количество простых в разложении числа до $$$2 \cdot 10^5$$$ не превосходит $$$25$$$. Для каждого $$$k$$$ от $$$0$$$ до $$$25$$$ построим массив префиксного предподсчета, $$$\mathtt{cnt}_{k, l}$$$ — количество чисел $$$\leqslant l$$$, имеющих ровно $$$k$$$ простых в разложении. Посчитать такой массив можно с помощью перехода $$$\mathtt{cnt}_{k, l} = \mathtt{cnt}_{k, l - 1} + (\mathrm{primes}(l) \overset{?}{=} k)$$$.

Теперь на запросы можно отвечать за $$$\mathcal{O}(1)$$$: на запрос $$$(k_i, l_i, r_i)$$$ достаточно вывести ответ $$$\mathtt{cnt}_{k, r} - \mathtt{cnt}_{k, l - 1}$$$.