Կատարյալ քառակուսիներ
Քառակուսային արմատների ( ) կախարդական աշխարհում որոշ թվեր «գրավիչ» են համարվում, եթե դրանք կատարյալ քառակուսիներ են (1, 4, 9, 16, 25, 36, 49 և այլն): Կատարյալ քառակուսիները ամբողջ թվերի քառակուսիներն են (օրինակ՝ 4-ը 2-ի քառակուսին է, 25-ը 5-ի քառակուսին է և այդպես շարունակ):
Ձեզ տրված է
n թվերի զանգված և q հարցումներ ձևաչափով «Քանի՞ գրավիչ թվեր կան միջակայքում»: Պահանջվում է գրել ծրագիր, որը հնարավորինս արագ կպատասխանի այդ հարցումներին:Մուտք
Մուտքի առաջին տողում տրված է երկու ամբողջ թիվ՝
n (զանգվածի տարրերի քանակը, 1 ≤ n ≤ ) և հարցումների քանակը q (1 ≤ q ≤ )։Հաջորդ տողում տրված են
n ամբողջ թվեր (բաժանված բացատներով), որոնք ներկայացնում են զանգվածի տարրերը ()։Հաջորդ
q տողերից յուրաքանչյուրում տրված է երկու ամբողջ թիվ և (0 ≤ ≤ < n), որոնք սահմանում են հարցման միջակայքը (ծայրակետերը ներառյալ)։Ելք
Ծրագիրը պետք է արտածի
q տող, որոնցից յուրաքանչյուրում պետք է տպի [; ] միջակայքում գտնվող գրավիչ (կատարյալ քառակուսի) թվերի քանակը:Օրինակներ
Մուտք | Ելք |
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