fhx 跟我说这题是简单题我就一眼秒了，没想到意思发现了标解以外的在线算法。

假设 $n,q,V$ 同阶。

对 $a$ 分块，块长为 $B$，散块部分直接暴力计算，复杂度为 $O(B)$。

对于整块的部分，考虑对询问的 $k$ 进行阈值分治，令阈值也为 $B$，查询的整块区间为 $L\sim R$ 块。

若 $k\le B$，预处理 $f_{i,j}$ 表示 $1\sim i$ 块中所有数除以 $k$ 下取整之和，则这部分就是 $f_{R,k}-f_{L-1,k}$。

若 $k> B$，枚举 $v\in [0,\lfloor\frac{V}{B}\rfloor]$ 表示存在多少个 $\lfloor\frac{a_i}{k}\rfloor=v$ 在整块区间内，转化为查询多少个值域在 $[vB,(v+1)B)$ 的数在整块区间里面，预处理 $g_{i,j}$ 表示前 $i$ 块 $\le j$ 的数的个数，也可以 $O(1)$ 求。

直接取 $B=\sqrt{n}$ 可以得到理论最优复杂度为 $O(n\sqrt{n})$，空间为 $O(n\sqrt{n})$。实际上对于第二问转化出来的询问离线处理也可以做到空间线性。

别看我，代码是 ds 写的。