DIVQUERY - editorial

No. You can do preprocessing when you load the array (it’s not changing). This part is in O(n*sqrt(MAXA)). Result of preprocessing is array of vectors, that for divisor k contains indexes of elements, divisor k divides.

Later when you have those list prepared, you can answer the query in O(log n) time using binary search in those lists…

1 Like

For input from problem statement lists are (if I didn’t do mistake somewhere):

2: 4 5 7 8
3: 1 5 6 7 8
4: 4 7
5: 2
6: 5 7 8
7: 
8: 
9: 6
10:
11:
12: 7
  • so there are two indexes in list 2 between 3 and 6 (first query)
  • in list 4 is one index between 3 6
  • list 3 - 4 items
  • list 7 - 0 items
  • list 6 - 1 item

and 2, 1, 4, 0, 1 is requested result

1 Like

thanks a lot
finally i got the concept.

u first created a list which is an array of vectors corresponding to each element from 2 to a_max of the given array and store all the indexes of elements which are divisible by k.

and then search(using binary search) how many elements are there between p1 and p2.

for eg for first query corresponding to k=2 there are two elements between 3 and 6.
corresponding to k=4 there is 1 element between 3 and 6
corresponding to k=3 there are 4 elements between 4 and 8
and so on…

exactly :wink:

can u please tell me the algorithm of above explanation.

In the tester’s solution, it is written:
“There is a known bound that integer N has at most O(n^(1/3))
divisors.”
Isn’t this bound wrong? When N = 83160, N has 128 divisors. But according to the bound by tester, N can have at most 43.6 divisors. Did I misunderstand the statement? What is the proof of the statement?

urm…, yep, you are right. guess it didnt matter because N was always same as Q, but good point.