TCP para la OCI

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem types

El concurso nacional de la OCI es un evento esperado con ansias por todos los programadores competitivos de preuniversitario que aspiran a formar parte de la PSN, y Sora no es la excepción. Con tal de tener más tiempo para estudiar, su profesor de matemáticas, Mario, le permitió convalidar el TCP si le demostraba su conocimiento en radicales, por lo que le propuso el siguiente ejercicio.

Dado un arreglo $R$ ~R~ de tamaño $N$ ~N~ $(1 \le N \le 2\times 10^5)$ ~(1 \le N \le 2\times 10^5)~, debe responder $Q$ ~Q~ $(1 \le Q \le 2\times 10^5)$ ~(1 \le Q \le 2\times 10^5)~ consultas con la siguiente forma. Dado 3 enteros positivos $l,r$ ~l,r~ $(1 \le l \le r \le 10^6)$ ~(1 \le l \le r \le 10^6)~ y $k$ ~k~ $(1 \le k \le 10^9)$ ~(1 \le k \le 10^9)~, diga la cantidad de números que cumplan las siguientes condiciones:

En la representación en factores primos (no vacía) del número, $p_{1}^{e_1}\times p_{2}^{e_2}\times p_{3}^{e_3}\times ...\times p_{n}^{e_n}$ , se debe cumplir que $l \le p_{i} \le r$ ~l \le p_{i} \le r~ y $1 \le e_i \le k$ ~1 \le e_i \le k~, o en otras palabras, cada factor primo debe tener un valor entre $l$ ~l~ y $r$ ~r~ (ambos inclusive) y un exponente menor o igual que $k$ ~k~.
El número debe tener raíz $R_i$ ~R_i~-ésima exacta para todo $1 \le i \le N$ ~1 \le i \le N~.

Se considera que un número $x$ ~x~ tiene raíz $i$ ~i~-ésima exacta cuando existe un número entero $y$ ~y~ tal que $y^i=x$ ~y^i=x~.

Como la cantidad de números puede ser muy grande imprima la respuesta a cada consulta módulo $10^9+7$ ~10^9+7~ $(1000000007)$ ~(1000000007)~.

Subtareas:

Subtarea 1: $l_j=r_j$ ~l_j=r_j~ $(1 \le j \le Q)$ ~(1 \le j \le Q)~, $N=1$ ~N=1~ (10 puntos).
Subtarea 2: $l_j=r_j$ ~l_j=r_j~ $(1 \le j \le Q)$ ~(1 \le j \le Q)~, $1 \le N\le 8$ ~1 \le N\le 8~, $1 \le R_i \le 300$ ~1 \le R_i \le 300~ (15 puntos).
Subtarea 3: La suma de $r_j - l_j + 1$ ~r_j - l_j + 1~ $(1 \le j \le Q)$ ~(1 \le j \le Q)~ es menor o igual que $2\times 10^5$ ~2\times 10^5~, $1 \le r \le 2\times 10^5$ ~1 \le r \le 2\times 10^5~, $1 \le N \le 8$ ~1 \le N \le 8~, $1 \le R_i \le 300$ ~1 \le R_i \le 300~ para todo $1 \le i \le N$ ~1 \le i \le N~ (25 puntos).
Subtarea 4: $N=1$ ~N=1~ (20 puntos).
Subtarea 5: Sin restricciones adicionales (30 puntos).

Entrada

La primera línea contiene un número entero $N$ ~N~ $(1\le N\le 2\times 10^5)$ ~(1\le N\le 2\times 10^5)~, la cantidad de números del arreglo $R$ ~R~.

En la segunda línea siguen $N$ ~N~ números enteros, las raíces $R_i$ ~R_i~ $(1\le R_i\le 10^9)$ ~(1\le R_i\le 10^9)~.

La tercera línea un entero $Q$ ~Q~ $(1\le Q\le 2\times 10^5)$ ~(1\le Q\le 2\times 10^5)~ el número de consultas.

Siguen $Q$ ~Q~ líneas cada una con 3 enteros $l,r$ ~l,r~ $(1\le l\le r\le 10^6)$ ~(1\le l\le r\le 10^6)~ y $k$ ~k~ $(1\le k\le 10^9)$ ~(1\le k\le 10^9)~.

Salida

La salida debe tener $Q$ ~Q~ líneas separadas por un salto de línea representando la respuesta a cada consulta, la cantidad de números que cumplan la condición módulo $10^9+7$ ~10^9+7~.

Ejemplo de entrada #1

Ejemplo de salida #1

En la primera consulta el único número que cumple la condición es el $125$ ~125~, porque $\sqrt[3]{125} = 5$ ~\sqrt[3]{125} = 5~, en la segunda y tercera consultas $20$ ~20~ y $24$ ~24~ no son primos así que ningún número cumple con la condición.

Ejemplo de entrada #2

Ejemplo de salida #2

3
0
4

En la primera consulta el conjunto de números que cumplen la condición es $\{64,729,46656\}$ ~\{64,729,46656\}~ ya que todos tienen en su representación en factores primos factores entre $2$ ~2~ y $4$ ~4~ con un exponente menor o igual que $7$ ~7~ y tienen raíz $1$ ~1~ra (el propio número, $\sqrt[1]{N} = N$ ~\sqrt[1]{N} = N~), raíz cuadrada $(\sqrt{64} = 8$ ~(\sqrt{64} = 8~, $\sqrt{729} = 27$ ~\sqrt{729} = 27~, $\sqrt{46656} = 216)$ ~\sqrt{46656} = 216)~, y raíz cúbica $(\sqrt[3]{64} = 4$ ~(\sqrt[3]{64} = 4~, $\sqrt[3]{729} = 9$ ~\sqrt[3]{729} = 9~, $\sqrt[3]{46656} = 36)$ ~\sqrt[3]{46656} = 36)~exactas.

Ejemplo de entrada #3

5
2 2 2 11 23
4
5 10 2021
15 20 2022
25 45 2023
50 100 2024

Ejemplo de salida #3

Comments

13
karellgz commented on Feb. 22, 2024, 11:44 p.m.
(Si quiere algun admin pasar este comentario a la editorial pues genial)

Esta es la via que yo halle para resolverlo por si alguien no le encuentra como hacerlo (intenten darle cabeza un rato antes de leer)

Subtarea 1

Para cada consulta: Digamos que existe un numero arbitrario $d=p^{\alpha _1}$ ~d=p^{\alpha _1}~ con $p$ ~p~ primo, y $\alpha_1 \le k$ ~\alpha_1 \le k~, necesariamente $l=p=r$ ~l=p=r~, por lo que primero debemos comprobar si $l$ ~l~ es primo, en caso de que no lo sea reportamos 0 para esta consulta pues no existe ningun numero de los buscados, en caso contrario, verificamos el otro requisito:

Sabemos que $d$ ~d~ tiene raiz $R_1$ ~R_1~-esima exacta, por lo que $R_1$ ~R_1~ debe dividir al exponente de $p$ ~p~ ( $\sqrt[R_1] {d} = p^{\frac \alpha {R_1} } \rightarrow R_1 | \alpha$ )

Yendo a lo que se nos pide, el problema se simplifica a: hallar la cantidad de numeros $d$ ~d~, osea la cantidad de multiplos de $R_1$ ~R_1~ menores o iguales a $k$ ~k~, que no es muy dificil llegar a que son exactamente $\lfloor \frac {k} {R_1} \rfloor$ ~\lfloor \frac {k} {R_1} \rfloor~ donde $\lfloor x \rfloor$ ~\lfloor x \rfloor~ indica el piso o parte entera de un numero.

Tiempo: $O(Q \cdot \sqrt l)$ ~O(Q \cdot \sqrt l)~

Subtarea 2

Utilizando la idea de arriba, como sabemos que $R_i$ ~R_i~ divide a $\alpha$ ~\alpha~ (Para todo $i \le N$ ~i \le N~), podemos concluir que el $mcm(R_1,...) | \alpha$ ~mcm(R_1,...) | \alpha~.

Realizamos el mismo procedimiento de la subtarea 1, pero trabajando en lugar de $R_1$ ~R_1~ con $mcm(R_1,R_2,...)$ ~mcm(R_1,R_2,...)~ , que se puede calcular en tiempo logaritmico.

Tiempo: $O( N \log R + Q \cdot \sqrt l \cdot)$ ~O( N \log R + Q \cdot \sqrt l \cdot)~

Subtarea 5

Por simplificar un poco lo que viene adelante digamos que $S = mcm(R_1,...)$ ~S = mcm(R_1,...)~

Luego, sea $t$ ~t~ la cantidad de primos en el intervalo $[l;r]$ ~[l;r]~, se puede calcular en tiempo logaritmico con la criba de Eratostenes.

Utilizando (y extendiendo) la idea anterior, pensemos en el nuevo numero $d=p_1^{\alpha_1}\cdot p_2 ^{\alpha_2}\cdot ... \cdot p_t^{\alpha _t}$ tambien sabemos que es valido si (y solo si) cada uno de sus exponentes es divisible por $S$ ~S~ por lo mencionado arriba.

Para llegar a la solucion puedes utilizar el siguiente procedimiento:

Contar la solucion para numeros con $1,2..,t$ ~1,2..,t~ primos

Utilizando el principio de multiplicacion, la solucion para algun $d$ ~d~ con digamos 1212 primos seria: $\lfloor \frac {k} {S} \rfloor^{1212}$ ~\lfloor \frac {k} {S} \rfloor^{1212}~

Entonces de nuevo con el principio de la multiplicacion, la cantidad de numeros $d$ ~d~ distintos con 1212 primos seria equivalente a decir, cuantas formas se puede escoger 1212 primos de un total de $t$ ~t~ primos, por la solucion para cada uno de ellos: $C^{t} _{1212} \lfloor \frac {k} {S} \rfloor^{1212}$

Sumar cada uno de los resultados

Deberia darte una respuesta correcta, aunque se iria de tiempo.

La suma $C^{t} _{1} \lfloor \frac {k} {S} \rfloor^{1} + C^{t} _{2} \lfloor \frac {k} {S} \rfloor^{2} + ... + C^{t} _{t} \lfloor \frac {k} {S} \rfloor^{t}$ (que es la que estas calculando) te debe parecer bastante conocida, y es que es practicamente la expansion del binomio $(a+b)^n$ ~(a+b)^n~

Y en efecto, con eso puedes calcular la solucion ahorrandote todas esas sumas con: $(\lfloor \frac {k} {S} \rfloor + 1)^t - 1 \mod 10^9+7$ (ejercicio para el lector decir el porque del $+1$ ~+1~ y del $-1$ ~-1~)

Tiempo:

$C =$ ~C =~ Tiempo para generar los primos hasta $10^6$ ~10^6~

$T =$ ~T =~ Tiempo para obtener la cantidad de primos, $O(n)$ ~O(n)~ si utilizas un bucle, $O(\log N)$ ~O(\log N)~ si utilizas busqueda binaria, $O(1)$ ~O(1)~ si utilizas un arreglo acumulativo

Tiempo final: $O(C + Q\cdot T \cdot \log t)$ ~O(C + Q\cdot T \cdot \log t)~

Thx4Read