Perfekte Quadratzahlen
Im faszinierenden Universum der Quadratwurzeln () wird eine Zahl als „attraktiv“ bezeichnet, wenn sie eine perfekte Quadratzahl ist (1, 4, 9, 16, 25, 36, 49 usw.). Perfekte Quadratzahlen ergeben sich aus dem Quadrat ganzer Zahlen (so ist 4 das Quadrat von 2 und 25 das Quadrat von 5 usw.).
Wenn wir
n Zahlen haben und q Anfragen der Form „Wie viele attraktive Zahlen gibt es im Bereich ?“, dann soll ein Programm entwickelt werden, das diese Fragen möglichst schnell beantwortet.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen –
n (die Anzahl der Elemente im Array, 1 ≤ n ≤ ) und q (die Anzahl der Anfragen, 1 ≤ q ≤ ).Die nächste Zeile enthält
n ganze Zahlen, getrennt durch Leerzeichen, die die Elemente des Arrays darstellen ().Anschließend folgen
q Zeilen, von denen jede zwei ganze Zahlen und (0 ≤ ≤ < n) enthält, die den geschlossenen Bereich der jeweiligen Abfrage angeben.Ausgabe
Das Programm soll
q Zeilen ausgeben, wobei jede Zeile die Anzahl der attraktiven Zahlen im Bereich enthält.Beispiele
Eingabe | Ausgabe |
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