How can I remove the loglog term from this?

Revision en1, by a_gt3_rs, 2024-10-21 07:59:31

Is this problem doable with less than $$$O(n\sqrt{n}log(log(n)))$$$ time?

Given an array $$$p$$$, assuming $$$p_i=O(n)$$$. The array is cut to $$$O(\sqrt{n})$$$ blocks.

There is only one kind of query:

$$$1\ i\ j\ k$$$: Count the numbers from block $$$i$$$ to block $$$j$$$ such that $$$p_k$$$ is a multiple of (the query must be done in $$$O(1)$$$).

Any help is appreciated.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English a_gt3_rs 2024-10-21 07:59:31 394 Initial revision (published)