Представим, что запросов деления нет. Построим дерево отрезков на произведение по модулю и будем отвечать на запросы за $$$O(\log n)$$$. Теперь научимся выполнять запрос деления. Заранее посчитаем решето Эратосфена, в котором сохраним для каждого числа его минимальный нечётный делитель, больший единицы или $$$-1$$$. Очевидно, что у каждого числа не больше $$$\log$$$ нечётных делителей, значит можно спускаться во все листья, которые изменятся. Как научиться определять, какие листья изменяться? Можно поддерживать в дереве отрезков количество степеней двойки в каждой вершине. Очевидно, что только у степеней двойки нет минимального нечётного делителя, большего единицы. Получили решение за $$$O(n \log \log n + m \log^2 n)$$$.