Les carrés parfaits
Dans l’univers magique des racines carrées (), un nombre est «attractif» s’il s’agit d’un carré parfait (1, 4, 9, 16, 25, 36, 49, etc.). Les carrés parfaits correspondent au carré d’un entier (par exemple, 4 est le carré de 2, 25 est le carré de 5, etc.).
Étant donné
n nombres et q requêtes de la forme «Combien de nombres attractifs se trouvent dans la plage ?», l’objectif est d’écrire un programme qui puisse répondre à ces questions aussi rapidement que possible.Entrée
La première ligne de l’entrée contient deux entiers :
n, le nombre d’éléments dans le tableau (1 ≤ n ≤ ), et q, le nombre de requêtes (1 ≤ q ≤ ).La ligne suivante contient
n entiers séparés par un espace, qui représentent les éléments du tableau .Chacune des
q lignes suivantes contient 2 entiers et (0 ≤ ≤ < n), indiquant la plage de la requête (inclusivement).Sortie
Le programme doit afficher
q lignes. Chaque ligne doit indiquer le nombre de nombres attractifs dans la plage .Exemples
Entrée | Sortie |
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