首先转化题意，发现其实需要求的就是 $\operatorname{lcm}(1,2,\dots,n)$ 的约数个数。
令 $x=\operatorname{lcm}(1,2,\dots,n)=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$，则有 $d(x)=\prod\limits_{i=1}^{k}(a_i+1)$。从小到大加入数的过程中，只有所有的 $p^k$（质数的整次幂）会对答案产生贡献。那么我们可以在筛质数的同时处理每个质数 $\le mx$ 的所有整次幂，用前缀积的形式维护答案。这样可以做到 $\mathcal O(mx)$ 预处理，$\mathcal O(1)$ 查询。
by XTianShuo @ 2022-11-04 08:03:52