Quadrati perfetti
Nell’universo magico delle radici quadrate (), un numero si definisce “attraente” se è un quadrato perfetto (1, 4, 9, 16, 25, 36, 49, ecc.). I quadrati perfetti sono i risultati del quadrato di un numero intero (ad esempio, 4 è il quadrato di 2, 25 è il quadrato di 5 e così via).
Dati
n numeri e q interrogazioni del tipo: “Quanti numeri attraenti si trovano nell’intervallo ?”, il compito è realizzare un programma che risponda a queste domande nel minor tempo possibile.Input
La prima riga di input contiene due interi:
n (il numero di elementi dell’array, con 1 ≤ n ≤ ) e q (il numero di interrogazioni, con 1 ≤ q ≤ ).La riga successiva contiene
n interi separati da uno spazio, che rappresentano gli elementi dell’array .Ciascuna delle successive
q righe contiene 2 interi e (0 ≤ ≤ < n), che rappresentano l’intervallo (inclusivo) della query.Output
Il programma deve stampare
q righe, ognuna contenente il numero di numeri attraenti presenti nell’intervallo .Esempi
Ingresso | Uscita |
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