Aclaraciones

1. ~\lfloor \frac{n}{k} \rfloor~ es la cantidad de múltiplos de ~k~ menores iguales que ~n~ sin contar al ~0~. Donde ~\lfloor x \rfloor~ indica la parte entera de un ~x~.
2. ~mcm(a,b)~ denota el mínimo común múltiplo entre ~a~ y ~b~.
3. Para este problema ~P(l,r)~ denota la cantidad de primos en ~[l,r]~.
4. El ~1~ no es parte de ninguna solución, ya que el conjunto de factores primos que lo componen sería un conjunto vacío (los exponentes de cada primo serían ~0~).

Subtarea 1

Como solo hay una raíz ~R_1~ y el rango ~[l,r]~ solo comprende un elemento, basta con comprobar si ~l~ es primo o no, comprobando si existe algún número ~x~ (~2 \le x \le \sqrt{l}~) tal que ~x | l~ (~x~ divide a ~l~).

Si ~l~ no es primo entonces la respuesta a esta consulta es ~0~, en caso contrario los números que cumplen la condición serían los números de la forma ~l^m~, donde ~m~ es múltiplo de ~R_1~, la cantidad de múltiplos de ~R_1~ menores iguales que ~k~ es ~\lfloor \frac{k}{R_1} \rfloor~ que sería la respuesta a la consulta.

Subtarea 2

Similar al razonamiento de la subtarea 1, solo que como aquí tenemos varias raíces, entonces la solución para ~l~ primo sería ~\frac{k}{mcm(R_1,R_2,...,R_N)}~ ya que solo para los números de la forma ~p^m~ con ~m~ múltiplo de ~R_i~, para todo ~1 \le i \le N~ se garantiza que existe un par de números ~\{a_1,a_2,...,a_N\}~ tal que ~a_i~ es de la forma ~p^{\frac{m}{R_i}}~; y ~(p^{\frac{m}{R_i}})^{R_i} = p^m~ por lo que queda demostrado que ~p^m~ tiene raíz ~R_i~-ésima exacta para todo ~1 \le i \le N~.

Subtarea 3

Como las restricciones son pequeñas, tanto para el tamaño de los rangos de las consultas como para el máximo valor que toma ~r~ en cada consulta, una solución por fuerza bruta entraría en tiempo.

La solución a cada consulta sería ~(\frac{k}{mcm(R_1,R_2,...,R_N)}+1)^{P(l,r)}-1~ ya que, como se explico en la subtarea 2 para un solo factor primo ~p~ existen ~\frac{k}{mcm(R_1,R_2,...,R_N)}~ posibles soluciones, con más de un factor primo, la cantidad de formas en que puedo escoger los exponentes ~e_i~ de los factores de la representación en factores primos del número ~p_1^{e_1}\times p_2^{e_2}\times ...\times p_n^{e_n}~ de tal forma que se cumplan las condiciones del problema, sería la fórmula planteada anteriormente, por el principio de multiplicación. El valor de ~P(l,r)~ se puede hallar iterando de ~l~ a ~r~ y comprobando para cada número si es primo, como se describe en la subtarea 1.

Subtarea 4

Como ~N=1~ la idea de la subtarea 1 funciona, solo que a eso hay que añadirle la cantidad de primos que hay en el rango ~[l,r]~ como se explica en la subtarea 3, por lo que la solución sería ~(\frac{k}{R_1}+1)^{P(l,r)}-1~. Para calcular ~P(l,r)~ eficientemente habría que usar una criba.

Subtarea 5

La respuesta a cada consulta es la misma que en la subtarea 3 solo que hay que hallar ~P(l,r)~ eficientemente como en la subtarea 4.