Auto comment: topic has been updated by UnfilledDreams (previous revision, new revision, compare).

I'll just determine T = 10⁵ to ease on writing, then we can say that A_i, N, Q ≤ T. What I currently have works in total time , if I'll find a better one I'll add it.

Since you're asking for "logic", I'll say how I think you should come up with this idea:

First, let's see that we can have multiple ways (though most of them are inefficient) to approach the queries, we'll focus on 2:

• We can do some preprocessing: for each value and each index, we can precompute the answer for the query on that value and position. The total query time is and the preprocessing is .
• We can do a different type of preprocessing: For each value in the array, we maintain a vector of its indicies in the array (also sorted; we just iterate from beginning to end). Then for a given X, i, for each multiple of X we do binary search on its vector of positions, to see how many indicies there are, which are at least i. This takes a total query time (in worst case) , and preprocessing .

The point is that approach 1 is heavy on preprocessing and light on query time, while approach 2 is the opposite. We can merge them. Let's determine a constant K:

• We will do approach 1 only on values that are less than K, and for queries with X < K we can solve them by approach 1. The total query time is while preprocessing is .
• We will do approach 2 only on values that are at least K, and solve with that queries for which X ≥ K. For some X in a query (which can be up to T) we binary search times, which is the worst case for X = K, so the total time on queries is and preprocessing is .

We want to pick a K for which the worst case between approach 1 and approach 2 is minimized. as K increases, approach 1 gets worse while approach 2 improves, so we would like to find a K for which approach 1 = approach 2:

: for this K, both approaches do in worst case total, .

Hopefully I didn't do too much :). This is pretty much sqrt-decomposition, but following only the idea and not the "sqrt" part.

Edit: one more thing to notice is that apporach 2 alone is worse than doing a simple brute force, but it's better in a sense because it can be easily improved using the constant K (which doesn't affect the brute force approach).

A simple solution here:

For each number precompute a vector of its divisors — . Keep an array C[i] = number of multiples of i. Now we start from the end of the array and answer all queries such that their i is equal to the current index we are looking at. Answer will obviously be C[X]. Also before answering the queries add +1 to all divisors of a[i]. The complexity is .