Modular Range Counting

Let $B=450$. For every $x\leq B$ and every remainder, store the sorted indices of elements having that remainder. Each element enters $B$ lists, so preprocessing time and memory are $O(NB)$.

For $x\leq B$, answer a query with two binary searches in the corresponding list. For $x>B$, since $A_i\leq B$, at most one value can have remainder ; use the list for that exact value.

Each query takes $O(\log N)$ time.

Solution written by GPT5