Números cuadrados perfectos
En el universo mágico de las raíces cuadradas (), un número se considera “atractivo” si es un cuadrado perfecto (1, 4, 9, 16, 25, 36, 49, etc.). Los cuadrados perfectos son aquellos que resultan de elevar un número entero al cuadrado (por ejemplo, 4 es el cuadrado de 2, 25 es el cuadrado de 5, etc.).
Dado
n números y q consultas de la forma “¿Cuántos números atractivos hay en el rango ?”, se solicita escribir un programa que responda esas preguntas lo más rápido posible.Entrada
La primera línea de la entrada contiene dos enteros:
n, la cantidad de elementos en el arreglo (1 ≤ n ≤ ) y q, el número de consultas (1 ≤ q ≤ ).La siguiente línea contiene
n enteros separados por un espacio, que representan los elementos del arreglo .Cada una de las siguientes
q líneas contiene 2 enteros y (0 ≤ ≤ < n) que indican el rango de la consulta (incluyente).Salida
El programa debe imprimir
q líneas, cada una con la cantidad de números atractivos que se encuentran en el rango .Ejemplos
Entrada | Salida |
6 4
9 5 2 4 16 3
0 5
0 1
1 2
2 5 | 3
1
0
2 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 5 MB