Números condicionalmente ricos

Submit solution
Points: 100 (partial)
Time limit: 0.2s
Memory limit: 64M
Author:
leocar
Problem type
Allowed languages
C++, Python

Descripción

Mariya tiene la siguiente definición para un número rico. Se da un entero postivo X. Un número entero positivo N es un número rico (relativo a X) si la suma de sus divisores exceptuando a N es mayor que X. Por ejemplo el número 10 (cuya suma de divisores es 1 + 2 + 5 = 8) es rico relativo a X = 7 pero no es rico relativo a X = 12.

Tarea

Escribe el programa para ayudar a Mariya. El programa recibirá consultas que son ternas de enteros positivos (L, R, V), por cada consulta se debe calcular la cantidad de números ricos relativos a V que son mayores o iguales a L y menores o iguales R.

Entrada

La primera línea de la entrada estándar contiene un entero positivo Q – El número de consultas que tu programa debe procesar. Las siguientes Q líneas contienen tres enteros positivos L, R y V, la consulta que tu programa debe procesar.

Salida

Tu programa debe imprimir Q líneas – una por cada consulta en la entrada. Cada línea debe contener la respuesta a la consulta respectiva.

Límites

  • 1 \le Q \le 10^5
  • 1 \le L \le R \le 10^5
  • 1 \le V \le 10^5

Subtareas

No | Subtarea | Puntos | Q | R | V | Otros límites

  1. 5 puntos | Q \le 10^3 | R \le 10^3 | V = 10^5 | Ninguno
  2. 10 puntos | Q \le 10^5 | R \le 10^4 | V = 10 | L = 1
  3. 30 puntos | Q \le 10^5 | R \le 10^5 | V = 10 | Ninguno
  4. 55 puntos | Q \le 10^5 | R \le 10^5 | V = 10^5 | 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


  • 0
    karellgz  commented on Feb. 14, 2024, 8:45 p.m.

    Alguien me puede decir que estructura o que es necesario usar para resolver este problema??


    • 2
      lrivero  commented on Feb. 15, 2024, 1:19 p.m.

      Puedes usar Segment tree o ABI


      • 1
        linkyless  commented on Feb. 17, 2024, 5:07 p.m.

        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?


        • 2
          karellgz  commented on Feb. 17, 2024, 9:14 p.m.

          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:

          • Generar la suma de divisores eficientemente
          • Segment Tree (+ Merge Sort)
          • Optimizar tremendamente todo ( Notese el enfasis )

          Otra ayuda: Para calcular eficientemente la cantidad de elementos mayores a un K, se puede utilizar una lista ordenada, pruebenlo en un ST

          Hope it helps!


      • 0
        karellgz  commented on Feb. 15, 2024, 10:29 p.m.

        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