Quadrados perfeitos
No universo mágico das raízes quadradas (), um número é considerado “atraente” se for um quadrado perfeito (1, 4, 9, 16, 25, 36, 49, etc.). Quadrados perfeitos são aqueles resultantes do quadrado de números inteiros (4 é o quadrado de 2, 25 é o quadrado de 5, etc.).
Dado
n números e q consultas no formato “Quantos números atraentes existem no intervalo ?”, pretende-se escrever um programa que responda a essas perguntas com a máxima eficiência.Entrada
A primeira linha da entrada contém dois inteiros –
n, o número de elementos do array (1 ≤ n ≤ ), e q, o número de consultas (1 ≤ q ≤ ).A linha seguinte contém
n números inteiros, separados por espaço, que representam os elementos do array .Cada uma das próximas
q linhas contém 2 inteiros e (0 ≤ ≤ < n), indicando o intervalo da consulta (inclusivo).Saída
O programa deve imprimir
q linhas, cada uma apresentando a quantidade de números atraentes no intervalo .Exemplos
Entrada | Saída |
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