Посчитаем $$$\text{rad}(n)$$$ и простые множители в разложении $$$\text{rad}(n)$$$ для $$$n$$$ до $$$10^6$$$ с помощью линейного решета Эратосфена. Тогда $$$\text{rad}(abc) = m$$$ разделим на все простые множители, входящие в $$$\text{rad}(a)$$$ и $$$\text{rad}(c)$$$, получим обязательные множители в $$$b$$$, которое обозначим за $$$r$$$.

Здесь важно отметить, что не гарантируется корректность $$$m$$$, то есть оно может содержать либо простое число, большее, чем $$$c$$$, либо делиться на квадрат простого, либо не делиться на нужные простые числа вообще. Также отдельным случаем можно было рассмотреть $$$m=1$$$, потому что в некоторых реализациях это могло иметь значение.

Теперь задача сводится к тому, чтобы найти такие числа $$$\lambda$$$, которые представимы в виде произведения простых множителей из $$$m$$$, возведенных в некоторые (неотрицательные) степени. Если простые множители обозначить за $$$p_i$$$, то $$$\lambda$$$ имеют такой вид: $$$$$$\lambda = p_1^{\alpha_1} \cdot p_2^{\alpha_2}\cdot \ldots \cdot p_k^{\alpha_k} $$$$$$

При этом степени вхождения простых чисел, которые делят число $$$r$$$ должны быть не менее $$$1$$$.

Как построить все такие числа $$$\lambda$$$? Для начала можно заметить, что количество различных простых в числе $$$abc$$$ не больше $$$14$$$. (Доказательство этого факта оставим как упражнение читателю).

Тогда можно построить рекурсию (что также можно назвать $$$\text{dfs}$$$ по числам), в которой мы будем домножать число на очередное простое и проверять, подходит ли текущее число в рекурсии под ограничения $$$a < \lambda < c$$$. Так как нам неважно в каком порядке будут рассматриваться простые множители, ведь $$$x \cdot y = y \cdot x$$$, можно перебирать в порядке неубывания.

Можно показать, что такая рекурсия будет работать примерно за $$$O(\sqrt{c}\log c)$$$. Доказательство этого факта не требовалось. Если вы дошли до факта, что различных простых в числе не больше $$$14$$$, то можно было запустить рекурсию для максимального теста — $$$a = 1, c = 10^6$$$ и количество простых $$$14$$$ (Естественно, это не сам максимальный тест, но что-то похожее, что поможет вам оценить количество операций). В результате получим, что в этом случае производится всего $$$\approx 54 \cdot 10^3$$$ операций, а для $$$t = 10^3$$$, количество операций будет $$$\approx 5 \cdot 10^7$$$. На языке $$$\text{C++}$$$ укладывается в ограничения по времени.

Время работы этого решения $$$O(t\sqrt{c}\log c)$$$.