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.