Números condicionalmente ricos
Descripción
Mariya tiene la siguiente definición para un número rico. Se da un entero postivo . Un número entero positivo es un número rico (relativo a ) si la suma de sus divisores exceptuando a es mayor que . Por ejemplo el número (cuya suma de divisores es = ) es rico relativo a = pero no es rico relativo a = .
Tarea
Escribe el programa para ayudar a Mariya. El programa recibirá consultas que son ternas de enteros positivos (, , ), por cada consulta se debe calcular la cantidad de números ricos relativos a que son mayores o iguales a y menores o iguales .
Entrada
La primera línea de la entrada estándar contiene un entero positivo – El número de consultas que tu programa debe procesar. Las siguientes líneas contienen tres enteros positivos , y , la consulta que tu programa debe procesar.
Salida
Tu programa debe imprimir líneas – una por cada consulta en la entrada. Cada línea debe contener la respuesta a la consulta respectiva.
Límites
Subtareas
No | Subtarea | Puntos | Q | R | V | Otros límites
- 5 puntos | | | | Ninguno
- 10 puntos | | | |
- 30 puntos | | | | Ninguno
- 55 puntos | | | | Ninguno
El puntaje de una subtarea solo se gana si se resuelven todos los casos para ella.
Ejemplo Entrada
3
5 15 5
1 20 20
12 20 10
Ejemplo Salida
6
2
4
Comments
Alguien me puede decir que estructura o que es necesario usar para resolver este problema??
Puedes usar Segment tree o ABI
Segment Tree estaría bien con un valor fijo de V, pero sin eso creo que no tengo ni idea de cómo meterlo aquí. ¿Hay alguna propiedad acaso o algo que no estoy viendo?
Nono osea, yo pensaba lo mismo que tu, pero si se puede resolver con ST (con BIT ni idea), solo que de una manera no tan obvia como los otros ejercicios, estos son unos hints por si tu o alguien mas necesita una ayuda:
Otra ayuda: Para calcular eficientemente la cantidad de elementos mayores a un , se puede utilizar una lista ordenada, pruebenlo en un ST
Hope it helps!
Thx, me puedes escribir al telegram? es que no tengo idea de como adaptar un ST a este problema :/
Edit: Forgetit, ya lo pude hacer, thx