0 mod X

$rev[x]=(A_i=x$となるような$i$、そのような$i$が存在しないなら-1$)$
$div[x]=\{i\ |\ A_i \equiv0\ (mod\ x)\}$
とします。

$M=max(A)$として、 $div[x](1\leq x \leq M)$は以下のように処理することで$O(M logM)$で全ての$x$について求めることができます。

for x in range(M + 1):
    if x == 0:
        continue
    for i in range(x, M + 1, x):
        if rev[i] != -1:
            div[x].append(rev[i])

次に、全ての$x$に対して、$div[x]$を昇順に並べ替えます。 あとは、クエリごとに、$L,R$について、$div[X]$を2分探索することにより、 この問題を全体で$O(M(logM)^2+QlogN)$で解くことができます。